WEBVTT

1
00:00:00.000 --> 00:00:08.567
This overview explains how common subexpression elimination
identifies matching structure and reuses a computed value.

2
00:00:08.567 --> 00:00:16.467
Avoiding repeated work requires a valid structural identity,
rather than a matching output on one convenient input.

3
00:00:16.767 --> 00:00:21.200
Two policy routes both require staff status and verification.

4
00:00:21.200 --> 00:00:24.800
The ordinary route also requires being in the office; the exception

5
00:00:24.800 --> 00:00:27.200
route requires special approval.

6
00:00:27.200 --> 00:00:33.700
Naming the shared condition S lets both routes refer to the same intermediate calculation.

7
00:00:33.700 --> 00:00:37.333
For a verified staff member, S is one.

8
00:00:37.333 --> 00:00:41.033
Store that value in a slot for this evaluation.

9
00:00:41.033 --> 00:00:45.433
The slot has a meaning and a lifetime: it holds the shared condition for the current

10
00:00:45.433 --> 00:00:50.467
input, not a permanent answer for all future requests.

11
00:00:50.467 --> 00:00:55.967
With office zero and exception one, the ordinary route returns zero while the exception

12
00:00:55.967 --> 00:00:57.867
route returns one.

13
00:00:57.867 --> 00:01:00.900
Both consume the same stored S.

14
00:01:00.900 --> 00:01:05.967
Their or returns one, so the request succeeds through the exception route.

15
00:01:05.967 --> 00:01:10.500
Sharing S preserves both route meanings.

16
00:01:10.500 --> 00:01:10.513
Common subexpression elimination identifies
matching structure and reuses the result.

17
00:01:10.513 --> 00:01:17.367
Common subexpression elimination identifies
matching structure and reuses the result.

18
00:01:17.367 --> 00:01:24.800
The repeated-subexpression rule contains two
written occurrences of S, which equals A AND B.

19
00:01:24.800 --> 00:01:31.433
Each occurrence has a structural key that
includes AND and the identities of its inputs.

20
00:01:31.433 --> 00:01:38.967
When the keys match under the chosen contract,
both occurrences refer to one result slot for S.

21
00:01:38.967 --> 00:01:45.600
The left branch reads that slot with C and D; the right reads it with E.

22
00:01:45.600 --> 00:01:50.933
At 11011 the final answer remains one.

23
00:01:50.933 --> 00:01:53.467
Across all 32 assignments,

24
00:01:53.467 --> 00:02:00.733
the teaching check gives identical outputs for
repeated computation and reuse of the saved value.

25
00:02:00.733 --> 00:02:08.967
Sharing a subtree does not automatically flatten
an associative chain, and it does not establish a time gain.

26
00:02:08.967 --> 00:02:13.600
Key construction and bookkeeping cost something too.

27
00:02:13.600 --> 00:02:20.300
This episode owns reuse of identical work; the next owns safe flattening.

28
00:02:20.613 --> 00:02:23.681
Return to the four-condition staff policy.

29
00:02:23.681 --> 00:02:32.497
S means staff and verified; L means S and office; R means S and exception; the answer is L or R.

30
00:02:32.497 --> 00:02:38.550
The intervening thirty-two-case check belongs to the separate five-input compiler example.

31
00:02:38.550 --> 00:02:45.110
Here staff, verified, office and exception are one, zero, one and one.

32
00:02:45.860 --> 00:02:49.370
The missing verification makes S zero.

33
00:02:49.370 --> 00:02:57.013
Both consumers use that same zero, so neither the office condition nor the exception condition can make its and route true.

34
00:02:57.013 --> 00:02:59.489
Their final or is zero.

35
00:02:59.489 --> 00:03:06.079
This verifies that sharing preserves a required condition instead of accidentally treating it as optional.

36
00:03:06.829 --> 00:03:10.280
This case establishes a specific contrast.

37
00:03:10.280 --> 00:03:13.302
Both routes still require S.

38
00:03:13.302 --> 00:03:15.953
Sharing must preserve the policy.

39
00:03:15.953 --> 00:03:22.098
Keep the input, intermediate values, and conclusion together when comparing it with the previous case.

40
00:03:22.098 --> 00:03:28.368
The calculated answer belongs to this complete assignment under the stated rule.

41
00:03:28.665 --> 00:03:33.032
A naive eager tree computes the shared condition twice.

42
00:03:33.032 --> 00:03:38.532
Common-subexpression elimination can remove one of those identical calculations.

43
00:03:38.532 --> 00:03:44.632
That is a structural saving we can count directly under the declared traversal model.

44
00:03:44.632 --> 00:03:48.865
The shared version also needs a way to keep and retrieve the result.

45
00:03:48.865 --> 00:03:52.932
For a large expensive subexpression that can be valuable.

46
00:03:52.932 --> 00:03:57.432
For a tiny operation, bookkeeping may offset the saved work.

47
00:03:57.432 --> 00:04:02.032
An instruction count alone does not measure that balance.

48
00:04:02.032 --> 00:04:06.032
First establish that the rewrite preserves every assignment.

49
00:04:06.032 --> 00:04:09.999
Then measure comparable complete tasks, with preparation

50
00:04:09.999 --> 00:04:12.865
and delivery handled consistently.

51
00:04:12.865 --> 00:04:20.025
A correct sharing transformation is not automatically a performance win on every workload.

52
00:04:20.025 --> 00:04:20.032
A correct sharing transformation is not automatically a performance win on every workload.

53
00:04:20.032 --> 00:04:24.799
Include both the operation and its inputs in the key.

54
00:04:24.799 --> 00:04:30.365
Account for lookup and bookkeeping before claiming a time gain.