Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Locality​ of​ Reference

Locality​ of​ Reference

What is Locality of Reference?
What problem for it?
How to resolve it?

--------

Lower layer studying meetup #1
https://nagoyabin.connpass.com/event/66865/

Kouji Matsui

October 28, 2017
Tweet

More Decks by Kouji Matsui

Other Decks in Programming

Transcript

  1. Kouji Matsui - kekyo • NAGOYA city, AICHI pref., JP

    • Twitter – @kekyo2 / Facebook • ux-spiral corporation • Microsoft Most Valuable Professional VS and DevTech 2015- • Certified Scrum master / Scrum product owner • Center CLR organizer. • .NET/C#/F#/IL/metaprogramming or like… • Bike rider
  2. Agenda •Physical side scales •Logical side scales •Data stream between

    physicals and logicals •Locality of reference •Anti-locality of reference •Conclusion
  3. 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
  4. 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)
  5. Agenda •Physical side scales •Logical side scales •Data stream between

    physicals and logicals •Locality of reference •Anti-locality of reference •Conclusion
  6. 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
  7. 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
  8. 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
  9. Agenda •Physical side scales •Logical side scales •Data stream between

    physicals and logicals •Locality of reference •Anti-locality of reference •Conclusion
  10. 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
  11. 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
  12. 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
  13. Agenda •Physical side scales •Logical side scales •Data stream between

    physicals and logicals •Locality of reference •Anti-locality of reference •Conclusion
  14. 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
  15. 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
  16. 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[]
  17. 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
  18. Agenda •Physical side scales •Logical side scales •Data stream between

    physicals and logicals •Locality of reference •Anti-locality of reference •Conclusion
  19. 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
  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 Common value Common value Common value Race condition (Receive coherence penalty) STRATEGY: • Turn to immutable • Hashed indexer Write back Write back
  21. Agenda •Physical side scales •Logical side scales •Data stream between

    physicals and logicals •Locality of reference •Anti-locality of reference •Conclusion
  22. Conclusion The execution context bounds not THREAD. The code executor

    is CPU CORE. CPU cores have structuable nested cache system. Cache miss penalty is large. Cache coherency penalty is large. Both I/O systems too. Important cache-related architecture: ◦ Locality of reference ◦ Immutable
  23. 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