Locality of Reference

What's "Locality of Reference?"
nagoya.bin meetup slide.

1. Locality
of
Reference
2017.10.28 NAGOYA.BIN#1 KOUJI MATSUI (@KEKYO2)

2. Kouji Matsui -kekyo
•NAGOYA city, AICHI pref., JP
•Twitter –@kekyo2/ Facebook
•ux-spiral corporation
•Microsoft Most Valuable Professional VS
and DevTech2015-
•Certified Scrum master / Scrum product
owner
•Center CLR organizer.
•.NET/C#/F#/IL/metaprogramming or like…
•Bike rider

3. Agenda
•Physical side scales
•Logical side scales
•Data stream between physicals and logicals
•Locality of reference
•Anti-locality of reference
•Conclusion

4. Physical side scales

5. Physical side scales
Processor #1
Physical Core #4
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #3
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #2
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Processor #2
Physical Core #8
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #7
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #6
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #5
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #17
Processor #3
Physical Core #12
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #11
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #10
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #1
Physical Core #9
Logical Core #1
Logical Core #1
Logical Core #1
Logical Core #33

6. Physical side scales
The memory/IO bind at
the fixed CPU/Core
(Non configurable)

7. Physical side scales
The “shared cache memory” bind at the fixed
CPU/Core
(Non configurable)

8. Physical side scales
The “cache memory” bind at the fixed CPU/Core
(Non configurable)
The “shared cache memory” bind at the fixed
CPU/Core
(Non configurable)

9. Agenda
•Physical side scales
•Logical side scales
•Data stream between physicals and logicals
•Locality of reference
•Anti-locality of reference
•Conclusion

10. Logical side scales
Process #1
Virtual
Memory
Space
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Process #2
Virtual
Memory
Space
Thread #1
Thread #1
Thread #1
Thread #1
Thread #11
Process #3
Virtual
Memory
Space
Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Process #4
Virtual
Memory
Space
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Process #5
Virtual
Memory
Space
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41

11. Logical side scales
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #11
Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
Logical Core #2
Logical Core #1
This is true story
Execution context

12. Logical side scales
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #11
Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
Logical Core #2
Logical Core #1
Switch execution
context

13. Agenda
•Physical side scales
•Logical side scales
•Data stream between physicals and logicals
•Locality of reference
•Anti-locality of reference
•Conclusion

14. Data stream between physicals and logicals
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #11
Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
Logical Core #2
Logical Core #1
L1/L2 cache #1
L1/L2 cache #2
L1/L2 cache #4
L1/L2 cache #3

15. Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #11
Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
Logical Core #2
Logical Core #1
L1/L2 cache #1
L1/L2 cache #2
L1/L2 cache #4
L3 cache #1 L3 cache #2
L1/L2 cache #3

16. Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #1
Thread #11
Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
Logical Core #2
Logical Core #1
L1/L2 cache #1
L1/L2 cache #2
L1/L2 cache #3
L1/L2 cache #4
L3 cache #1 L3 cache #2
NUMA node bound memory

17. Agenda
•Physical side scales
•Logical side scales
•Data stream between physicals and logicals
•Locality of reference
•Anti-locality of reference
•Conclusion

18. Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
L1/L2 cache #4
L3 cache #2
NUMA node bound memory
declaredType
currentType
stopType
field
FieldInfo[]
Thread #33 context
Load/Preload

19. Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
L1/L2 cache #4
L3 cache #2
NUMA node bound memory
__stack0_0
Thread #42 context
__stack0_1
__stack0_2
__stack1_0
declaredType
currentType
local0
local1
field
Load/Preload
Switch

20. Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
L1/L2 cache #3
L1/L2 cache #4
L3 cache #2
NUMA node bound memory
declaredType
currentType
stopType
field
FieldInfo[]

21. Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
L1/L2 cache #3
L1/L2 cache #4
L3 cache #2
NUMA node bound memory
declaredType
currentType
stopType
field
FieldInfo[]
stopType
field
FieldInfo[]
field
Load/Preload
Switch

22. Agenda
•Physical side scales
•Logical side scales
•Data stream between physicals and logicals
•Locality of reference
•Anti-locality of reference
•Conclusion

23. Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
L1/L2 cache #3
L1/L2 cache #4
L3 cache #2
NUMA node bound memory
Common value
Common value
Common value
Load/Preload
Load/Preload
These threads access
common value

24. Thread #1
Thread #1
Thread #1
Thread #1
Thread #21
Thread #1
Thread #1
Thread #1
Thread #1
Thread #31
Thread #1
Thread #1
Thread #1
Thread #1
Thread #41
Logical Core #4
Logical Core #3
L1/L2 cache #3
L1/L2 cache #4
L3 cache #2
NUMA node bound memory
Common value
Common value
Common value
Race condition
(Receive coherence penalty)
STRATEGY:
•Turn to immutable
•Hashed indexer
Write back
Write back

25. Agenda
•Physical side scales
•Logical side scales
•Data stream between physicals and logicals
•Locality of reference
•Anti-locality of reference
•Conclusion

26. Conclusion
The execution context bounds not THREAD. The code executor is
CPU CORE.
CPU cores have structuablenested cache system.
Cache misspenalty is large.
Cache coherencypenalty is large.
Both I/O systemstoo.
Important cache-related architecture:
◦Locality of reference
◦Immutable

27. Thanks join!
My blog
◦http://www.kekyo.net/
Current active project:
◦IL2C -A translator implementation of .NET intermediate language to C
language.
◦YouTube:http://bit.ly/2xtu4MH
◦GitHub:https://github.com/kekyo/IL2C