Ruby 2.4 のハッシュテーブル高速化を理解する

第2回 meguro.rb LT で Ruby 2.4 のハッシュテーブル実装について話しました
https://megurorb.connpass.com/event/55107/

Transcript

1. 3VCZ
   
   ͷϋογϡςʔϒϧ
   ߴ଎ԽΛཧղ͢Δ
   
   /BP
   .JOBNJ
   !TPVUI
2. ࣗݾ঺հ
3. /BP
   .JOBNJ
   
   !TPVUI
   !NJOBNJP 4PGUXBSF
   FOHJOFFS
   
   !
   8BOUFEMZ
   *OD
4. w 
   
   3VCZ
   ͱύϑΥʔϚϯε
   w 
   
   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
   w 
   
   ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
   w 
   
   ·ͱΊ ࠓ೔࿩͢಺༰
5. w 
   
   3VCZ
   ͱύϑΥʔϚϯε
   w 
   
   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
   w 
   
   ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
   w 
   
   ·ͱΊ ࠓ೔࿩͢಺༰
6. 3VCZ
   Y
7. w ೥·Ͱʹ
   3VCZ
   ͸ഒ଎͘ͳΔ
   CZ
   !NBU[ 
   3VCZ
   ͱύϑΥʔϚϯε w .VMUJ
   5ISFBE
   +*5
   FUD
   w 3VCZ
   Y w 3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎Խ /&8
8. w 
   
   3VCZ
   ͱύϑΥʔϚϯε
   w 
   
   3VCZ
   
   Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
   w 
   
   ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
   w 
   
   ·ͱΊ ࠓ೔࿩͢಺༰
9. 
   ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
10. 
    ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
11. 
    ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ w 36#:#&/$)
    w 
    ߴ଎Խ
    w ϝϞϦ࢖༻ྔ
    
    ࡟ݮ 1000000.times.map{|i| a={}; 8.times{|j| a[j]=j}; a} IUUQTSVCZCFODIPSHSVCZSVCZSFMFBTFT SFTVMU@UZQFIBTI@TNBMM
12. 
    ϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ w QJDP@IUUQ@QBSTFS
    w 
    ߴ଎Խ IUUQLB[FCVSPIBUFOBCMPHDPNFOUSZ
    ྘
    ʜ
    3VCZ
    
    ੨
    ʜ
    3VCZ
    QSF
13. ܶతʹ଎͘ͳͬͯΔ
14. w 
    
    3VCZ
    ͱύϑΥʔϚϯε
    w 
    
    3VCZ
    
    Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
    w 
    
    ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
    w 
    
    ·ͱΊ ࠓ೔࿩͢಺༰
15. 
    ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ w ϋογϡςʔϒϧͷিಥ࣌ͷڍಈΛมߋ $IBJOJOH 0QFO
    "ESFTTJOH w ϙΠϯτ͸ʮσʔλͷہॴੑͷ޲্ʯ
16. 
    σʔλͷہॴੑ͸ͳͥॏཁ͔ w 1SPDFTTPS
    ʹ͸ଟஈΩϟογϡ͕ଘࡏ
    w Ωϟογϡʹ
    IJU
    ͢ΔͱύϑΥʔϚϯε޲্ $16 L# .BJO
    .FNPSZ -
    $BDIF -
    $BDIF -
    $BDIF .# (# L# #
    d
    
    OT IUUQTUBDLPWFSqPXDPNRVFTUJPOTBQQSPYJNBUFDPTUUPBDDFTTWBSJPVTDBDIFTBOENBJONFNPSZ d
    OT
17. 
    σʔλͷہॴੑ͸ͳͥॏཁ͔ w 1SPDFTTPS
    ʹ͸ଟஈΩϟογϡ͕ଘࡏ
    w σʔλͷہॴੑ͕ॏཁ $16 L# .BJO
    .FNPSZ -
    $BDIF -
    $BDIF -
    $BDIF .# (# L# #
    d
    
    OT IUUQTUBDLPWFSqPXDPNRVFTUJPOTBQQSPYJNBUFDPTUUPBDDFTTWBSJPVTDBDIFTBOENBJONFNPSZ d
    OT
18. 
    0QFO
    "ESFTTJOH
    Ͱσʔλͷہॴੑ্͕͕Δͷ͸ͳͥʁ w $IBJOJOH
    0QFO
    "ESFTTJOH
    ͭͷΞϧΰϦζϜΛൺֱ w ૬ҧ఺
    ϋογϡςʔϒϧͷিಥ࣌ͷڍಈ
    w $IBJOJOH
    
    ࿈݁ϦετΛḷͬͯ୳ࡧ
    w 0QFO
    "ESFTTJOH
    
    "SSBZ
    ্Ͱ
    JOEFY
    Λม͑ͯ୳ࡧ w ڞ௨఺
    w ϋογϡςʔϒϧ͸
    LFZ
    ͷ
    IBTI
    ஋
    Λ
    JOEFY
    ʹར༻
19. 
    $IBJOJOH
    ͷ࢓૊Έ w UBCMF
    ͸࿈݁Ϧετ΁ͷϙΠϯλΛอ࣋
    w ಉ͡
    IBTI
    Λ࣋ͭ৔߹͸ɺ࿈݁ϦετΛḷΔ IUUQXXXBMHPMJTUOFU%BUB@TUSVDUVSFT)BTI@UBCMF$IBJOJOH FOUSZ UBCMF LFZ
20. 
    $IBJOJOH
    ͷ໰୊఺ w ࿈݁ϦετͷFOUSZ͸ɺNFNPSZ্Ͱ཭Εͯ഑ஔ
    w σʔλͷہॴੑ͕௿͍ FOUSZ UBCMF LFZ
21. 
    3VCZ
    
    Ҏલͷ
    $IBJOJOH w ૒ํ޲Ϧετʹͳ͓ͬͯΓɺσʔλͷہॴੑ͕௿͍ ͚ͩͰͳ͘QSFW
    ϙΠϯλͳͲͷ෼͚ͩ
    FOUSZ
    ͷσʔ λ͕Ͱ͔͍ͷ΋໰୊ IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSETGBTUFSSVCZIBTIUBCMFT UBCMF FOUSZ FOUSZ FOUSZ
22. 
    3VCZ
    
    Ҏલͷ
    $IBJOJOH w ૒ํ޲Ϧετʹͳ͓ͬͯΓɺσʔλͷہॴੑ͕௿͍ ͚ͩͰͳ͘QSFW
    ϙΠϯλͳͲͷ෼͚ͩ
    FOUSZ
    ͷσʔ λ͕Ͱ͔͍ͷ΋໰୊ IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSETGBTUFSSVCZIBTIUBCMFT UBCMF FOUSZ FOUSZ FOUSZ ஗͍
23. 
    0QFO
    "ESFTTJOH
    ͷ࢓૊Έ w UBCMF
    ͸
    FOUSZ
    ΁ͷ
    QPJOUFS
    Λ௚઀อ࣋
    w ಉ͡
    IBTI
    Λ࣋ͭ৔߹͸ɺJOEFY
    ΛͣΒ͢ FOUSZ UBCMF LFZ IUUQXXXBMHPMJTUOFU%BUB@TUSVDUVSFT)BTI@UBCMF0QFO@BEESFTTJOH
24. 
    3VCZ
    
    ͷ
    0QFO
    "ESFTTJOH UBCMF FOUSJFT TUBSU CPVOE w UBCMF
    FOUSJFT
    ͕྆ํ
    "SSBZ
    ʹͳ͓ͬͯΓσʔλͷہॴ ੑ͕ߴ͘ɺ
    ͭͭͷ
    FOUSZ
    ͷσʔλαΠζ΋খ͍͞ IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSETGBTUFSSVCZIBTIUBCMFT
25. 
    3VCZ
    
    ͷ
    0QFO
    "ESFTTJOH UBCMF FOUSJFT TUBSU CPVOE w UBCMF
    FOUSJFT
    ͕྆ํ
    "SSBZ
    ʹͳ͓ͬͯΓσʔλͷہॴ ੑ͕ߴ͘ɺ
    ͭͭͷ
    FOUSZ
    ͷσʔλαΠζ΋খ͍͞ ߴ଎Խ
26. 
    3VCZ
    
    Ͱ͸ߋʹࡉ͔͘࠷దԽ w ݅਺͕গͳ͍࣌ͷ࠷దԽʢলϝϞϦɺߴ଎Խʣ
    w ݅਺͕গͳ͍࣌͸
    BSSBZ
    ͭͰ
    MJOFBS
    TFBSDI
    w ݅਺͕গͳ͍࣌͸
    CJU
    CJU
    ͳͲͰ
    JOEFY
    Λදݱ w 'VMM
    DZDMF
    MJOFBS
    DPOHSVFOUJBM
    HFOFSBUPS
    Λ
    TFDPOEBSZ
    IBTI
    ͱͯ͠ར༻
    w ߴ଎͔ͭ
    IBTI
    ͱͯ͠ͷੑೳ΋ྑ͍
27. w 
    
    3VCZ
    ͱύϑΥʔϚϯε
    w 
    
    3VCZ
    
    Ͱͷϋογϡςʔϒϧߴ଎ԽͱͦͷԸܙ
    w 
    
    ߴ଎Խ͸Ͳ͏࣮ݱ͞Εͨͷ͔ʁ
    w 
    
    ·ͱΊ ࠓ೔࿩͢಺༰
28. 
    ·ͱΊ w 3VCZ
    
    ͸ϋογϡςʔϒϧ͕ܶతʹߴ଎Խɻ࣮ࡍ ʹΞϓϦέʔγϣϯ΋ߴ଎Խɻ
    w 3VCZ
    
    ʹͯ͠շదͳ
    3VCZ
    ϥΠϑΛૹΖ͏ʂ
29. ࢀߟϦϯΫ w 3VCZ
    
    ϦϦʔε
    w IUUQTXXXSVCZMBOHPSHKBOFXT SVCZSFMFBTFE
    w 'FBUVSF
    
    )BTI
    UBCMFT
    XJUI
    PQFO
    BESFTTJOH
    w IUUQTCVHTSVCZMBOHPSHJTTVFT
    w 5PXBSET
    'BTUFS
    3VCZ
    )BTI
    5BCMFT
    w IUUQTEFWFMPQFSTSFEIBUDPNCMPHUPXBSET GBTUFSSVCZIBTIUBCMFT