WEBVTT

1
00:00:00.300 --> 00:00:04.900
A compiler can reorganize an expression without changing its answers.

2
00:00:04.900 --> 00:00:09.133
Two useful ideas are sharing a repeated calculation and flattening a chain

3
00:00:09.133 --> 00:00:11.567
of the same operation.

4
00:00:11.567 --> 00:00:17.300
They solve different problems, and a careless flattening step can undo useful sharing.

5
00:00:17.300 --> 00:00:21.300
We will build one access rule, transform its graph, and follow the

6
00:00:21.300 --> 00:00:24.300
values through each version.

7
00:00:24.300 --> 00:00:29.300
We will also count instructions and elementary combinations separately.

8
00:00:29.300 --> 00:00:34.533
That distinction explains why a shorter instruction list is not automatically less work or

9
00:00:34.533 --> 00:00:37.187
a faster program.

10
00:00:37.187 --> 00:00:37.200
a faster program.

11
00:00:37.500 --> 00:00:40.567
Our fictional rule has five inputs.

12
00:00:40.567 --> 00:00:45.967
The letter A means approved staff, and B means identity verified.

13
00:00:45.967 --> 00:00:49.800
Both are required for every permitted request.

14
00:00:49.800 --> 00:00:54.133
C means within access hours, and D means at the office.

15
00:00:54.133 --> 00:00:58.133
These two conditions define the ordinary access route.

16
00:00:58.133 --> 00:01:03.900
E means special approval, which provides an alternative route.

17
00:01:03.900 --> 00:01:09.567
Each input is a yes-or-no condition, encoded as one or zero.

18
00:01:09.567 --> 00:01:14.786
We will keep these meanings visible while the letters become part of the graph.

19
00:01:14.786 --> 00:01:14.800
We will keep these meanings visible while the letters become part of the graph.

20
00:01:15.100 --> 00:01:19.100
First compute S: approved staff and verified identity.

21
00:01:19.100 --> 00:01:23.233
Next compute P: within access hours and at the office.

22
00:01:23.233 --> 00:01:26.933
The ordinary route, L, requires both S and P.

23
00:01:26.933 --> 00:01:31.033
The special route, R, requires S and special approval E.

24
00:01:31.033 --> 00:01:35.433
Both routes depend on the same eligibility condition S.

25
00:01:35.433 --> 00:01:38.600
The final result F is L or R.

26
00:01:38.600 --> 00:01:42.667
This is inclusive or: either route can allow access, and having both

27
00:01:42.667 --> 00:01:46.253
routes true also allows access.

28
00:01:46.253 --> 00:01:46.267
routes true also allows access.

29
00:01:46.567 --> 00:01:52.300
Use inputs one, one, zero, one, one in A through E order.

30
00:01:52.300 --> 00:01:55.267
S is one and one, giving one.

31
00:01:55.267 --> 00:01:58.967
P is zero and one, giving zero.

32
00:01:58.967 --> 00:02:03.733
The ordinary route combines S one with P zero, giving zero.

33
00:02:03.733 --> 00:02:08.800
The special route combines S one with E one, giving one.

34
00:02:08.800 --> 00:02:12.033
Finally, zero or one gives one.

35
00:02:12.033 --> 00:02:14.967
Access is allowed through the special route.

36
00:02:14.967 --> 00:02:18.067
Keep these intermediate values; they will let us check every

37
00:02:18.067 --> 00:02:22.231
transformation against the same request.

38
00:02:22.231 --> 00:02:22.233
transformation against the same request.

39
00:02:22.533 --> 00:02:27.133
Written out separately, the two routes both contain A and B.

40
00:02:27.133 --> 00:02:32.133
A direct evaluation of each written copy can repeat that calculation.

41
00:02:32.133 --> 00:02:38.500
Common subexpression elimination, or C S E, recognizes matching expression structure and

42
00:02:38.500 --> 00:02:41.900
gives the common calculation one result slot.

43
00:02:41.900 --> 00:02:45.867
Both routes can read S from that slot.

44
00:02:45.867 --> 00:02:49.200
The current baseline uses structural matching.

45
00:02:49.200 --> 00:02:53.800
It does not need the two written occurrences to be the same object in memory.

46
00:02:53.800 --> 00:02:59.328
This is distinct from proving arbitrary differently written formulas equivalent.

47
00:02:59.328 --> 00:02:59.333
This is distinct from proving arbitrary differently written formulas equivalent.

48
00:02:59.633 --> 00:03:03.200
Now consider an and chain on its own.

49
00:03:03.200 --> 00:03:08.467
Both groupings require A, B, and C all to be one.

50
00:03:08.467 --> 00:03:12.933
That is why changing the parentheses preserves the answer for every input, not

51
00:03:12.933 --> 00:03:15.767
just for a few examples.

52
00:03:15.767 --> 00:03:23.033
For inputs one, one, zero, the left grouping first computes one and one, giving one.

53
00:03:23.033 --> 00:03:27.233
The right grouping first computes one and zero, giving zero.

54
00:03:27.233 --> 00:03:30.533
Both complete calculations finish at zero.

55
00:03:30.533 --> 00:03:34.233
For three ones, both finish at one.

56
00:03:34.233 --> 00:03:38.967
We can represent the chain as one instruction with three operands.

57
00:03:38.967 --> 00:03:44.800
Under the simple binary evaluation we are counting, it still takes two combinations.

58
00:03:44.800 --> 00:03:49.784
One instruction does not mean one binary operation.

59
00:03:49.784 --> 00:03:49.800
One instruction does not mean one binary operation.

60
00:03:50.100 --> 00:03:52.667
Return to our access graph.

61
00:03:52.667 --> 00:03:56.633
A consumer is an operation that uses a computed value.

62
00:03:56.633 --> 00:04:00.900
L uses S, and R also uses S.

63
00:04:00.900 --> 00:04:04.000
S therefore has two consumer edges.

64
00:04:04.000 --> 00:04:06.633
P is used only by L.

65
00:04:06.633 --> 00:04:10.967
P has one consumer, and both P and L perform and.

66
00:04:10.967 --> 00:04:17.067
P is the private same-operation child we can absorb into its parent.

67
00:04:17.067 --> 00:04:22.133
These two observations must be made together: the operation matches, and the child has

68
00:04:22.133 --> 00:04:24.267
only one consumer.

69
00:04:24.267 --> 00:04:27.833
The current sharing-aware baseline uses that distinction when

70
00:04:27.833 --> 00:04:31.466
it flattens associative chains.

71
00:04:31.466 --> 00:04:31.467
it flattens associative chains.

72
00:04:31.767 --> 00:04:37.567
Replace the reference to private P inside L with P's operands, C and D.

73
00:04:37.567 --> 00:04:43.067
L becomes a three-input and of S, C, and D.

74
00:04:43.067 --> 00:04:47.000
P no longer needs its own instruction in this plan.

75
00:04:47.000 --> 00:04:50.067
Its work has been incorporated into L.

76
00:04:50.067 --> 00:04:54.433
The inputs C and D have not vanished.

77
00:04:54.433 --> 00:04:57.567
Leave S as a separate shared value.

78
00:04:57.567 --> 00:04:59.800
Both routes still read it.

79
00:04:59.800 --> 00:05:03.200
We have flattened the private chain while preserving the calculation

80
00:05:03.200 --> 00:05:06.562
that serves two consumers.

81
00:05:06.562 --> 00:05:06.567
that serves two consumers.

82
00:05:06.867 --> 00:05:09.133
Run the same request again.

83
00:05:09.133 --> 00:05:11.033
S remains one.

84
00:05:11.033 --> 00:05:16.533
For the flattened left instruction, combine S one with C zero to get zero, then combine

85
00:05:16.533 --> 00:05:18.967
that zero with D one.

86
00:05:18.967 --> 00:05:21.967
L remains zero.

87
00:05:21.967 --> 00:05:26.633
R still combines the shared S one with E one, giving one.

88
00:05:26.633 --> 00:05:32.667
F combines zero or one, so the final answer remains allow.

89
00:05:32.667 --> 00:05:35.700
This trace explains the example.

90
00:05:35.700 --> 00:05:41.200
Separately, we checked all thirty-two assignments of the five independent inputs.

91
00:05:41.200 --> 00:05:45.895
The original and flattened plans agree on every one.

92
00:05:45.895 --> 00:05:45.900
The original and flattened plans agree on every one.

93
00:05:46.200 --> 00:05:50.300
Suppose we also splice S into both consumers.

94
00:05:50.300 --> 00:05:54.367
L becomes an and of A, B, C, and D.

95
00:05:54.367 --> 00:05:58.000
R becomes an and of A, B, and E.

96
00:05:58.000 --> 00:06:02.667
These expressions still describe the same Boolean function.

97
00:06:02.667 --> 00:06:08.567
But in the simple instruction execution shown here, the left instruction combines A and B,

98
00:06:08.567 --> 00:06:12.400
and the right instruction combines A and B again.

99
00:06:12.400 --> 00:06:16.900
The shared calculation has been duplicated.

100
00:06:16.900 --> 00:06:23.033
We are not adding another optimization pass that rediscovers the common calculation.

101
00:06:23.033 --> 00:06:26.367
Under this stated plan, splicing the shared child preserves

102
00:06:26.367 --> 00:06:30.591
correctness while losing useful reuse.

103
00:06:30.591 --> 00:06:30.600
correctness while losing useful reuse.

104
00:06:30.900 --> 00:06:37.033
The original shared plan has five operator instructions, each combining two values.

105
00:06:37.033 --> 00:06:40.000
That gives five binary combinations.

106
00:06:40.000 --> 00:06:44.467
We are counting operator instructions, not input loads.

107
00:06:44.467 --> 00:06:49.000
After flattening only P, there are four operator instructions.

108
00:06:49.000 --> 00:06:55.533
S takes one combination, L takes two, R takes one, and F takes one.

109
00:06:55.533 --> 00:06:58.633
The total is still five.

110
00:06:58.633 --> 00:07:03.133
After also splicing S, there are three operator instructions.

111
00:07:03.133 --> 00:07:08.367
L now takes three combinations, R takes two, and F takes one.

112
00:07:08.367 --> 00:07:10.667
The total has risen to six.

113
00:07:10.667 --> 00:07:16.567
The shortest instruction list does more binary combining in this example.

114
00:07:16.867 --> 00:07:22.367
Now remove special approval by changing only E from one to zero.

115
00:07:22.367 --> 00:07:28.967
S is still one, and the ordinary route is still zero because C is zero.

116
00:07:28.967 --> 00:07:33.500
The right route now computes one and zero, giving zero.

117
00:07:33.500 --> 00:07:37.733
The final result is zero or zero, which is zero.

118
00:07:37.733 --> 00:07:42.033
All three plans deny this request.

119
00:07:42.033 --> 00:07:46.633
Their outputs change together because they implement the same function.

120
00:07:46.633 --> 00:07:50.400
Their instruction structure and repeated work differ.

121
00:07:50.400 --> 00:07:54.900
Those are the properties the transformation is changing.

122
00:07:55.200 --> 00:07:58.100
The same-operation condition matters.

123
00:07:58.100 --> 00:08:02.233
Consider A and the grouped expression B or C.

124
00:08:02.233 --> 00:08:05.900
The child is or, while the parent is and.

125
00:08:05.900 --> 00:08:09.667
Set A to zero and both B and C to one.

126
00:08:09.667 --> 00:08:16.767
Inside the original grouping, B or C gives one, and A and one gives zero.

127
00:08:16.767 --> 00:08:22.733
Changing the expression to A and B, then or C, gives zero or one, which is one.

128
00:08:22.733 --> 00:08:24.333
The answer changed.

129
00:08:24.333 --> 00:08:29.419
That is not the valid associative flattening we have been using.

130
00:08:29.419 --> 00:08:29.433
That is not the valid associative flattening we have been using.

131
00:08:29.733 --> 00:08:35.333
The current structural C S E baseline follows this sharing-aware rule.

132
00:08:35.333 --> 00:08:40.833
In this teaching expression, its actual emitted operator counts match the original and

133
00:08:40.833 --> 00:08:44.333
private-only plans we have shown.

134
00:08:44.333 --> 00:08:48.267
The always-splice plan is our explicit contrast.

135
00:08:48.267 --> 00:08:54.000
Its extra binary combination explains a possible source of wasted work; it is not the

136
00:08:54.000 --> 00:08:57.500
production baseline being relabeled.

137
00:08:57.500 --> 00:09:01.233
None of these counts is an elapsed-time measurement.

138
00:09:01.233 --> 00:09:06.400
To claim a speed difference, compare the actual implementations with the same inputs,

139
00:09:06.400 --> 00:09:10.684
outputs, lifecycle, and timed boundary.

140
00:09:10.684 --> 00:09:10.700
outputs, lifecycle, and timed boundary.

141
00:09:11.000 --> 00:09:15.433
Sharing gives a common calculation one reusable value.

142
00:09:15.433 --> 00:09:21.700
Flattening merges a private chain of the same associative operation into its parent.

143
00:09:21.700 --> 00:09:26.833
Use both ideas together: absorb private chains while protecting children whose values

144
00:09:26.833 --> 00:09:30.167
serve more than one consumer.

145
00:09:30.167 --> 00:09:35.167
Then check the answers, read instruction and operation counts separately, and measure

146
00:09:35.167 --> 00:09:37.167
before claiming speed.

147
00:09:37.167 --> 00:09:40.933
That is how flattening can simplify a program's organization without

148
00:09:40.933 --> 00:09:44.951
silently giving away its sharing.