Ускоряем sync.Map на 73% за 40 строк кода

Данный способ — это всего лишь спортивный эксперимент, накиданный под вечер на коленке с целью что-нибудь исследовать.

Задача была написать аналог sync.Map максимально приближенный по производительности к оригиналу, спортивного интереса ради.

Давайте сразу к коду и бенчмаркам:

package main  import ( "hash/fnv" "sync" )  type bucket struct { data sync.Map }  type FastSyncMap struct { buckets []*bucket }  func NewSyncMap(bucketCount int) *FastSyncMap { buckets := make([]*bucket, bucketCount) for i := range buckets { buckets[i] = &bucket{} } return &FastSyncMap{buckets: buckets} }  func (m *FastSyncMap) hash(key string) int { h := fnv.New32a() h.Write([]byte(key)) return int(h.Sum32()) % len(m.buckets) }  func (m *FastSyncMap) Store(key string, value interface{}) { index := m.hash(key) b := m.buckets[index] b.data.Store(key, value) }  func (m *FastSyncMap) Load(key string) (value interface{}, ok bool) { index := m.hash(key) b := m.buckets[index] return b.data.Load(key) }

Вот так выглядит бенчмарк:

package main  import ( "strconv" "sync" "testing" )  var data = map[string]int{ "key-001": 437, "key-002": 384, "key-003": 983, "key-004": 543, "key-005": 276, "key-006": 128, "key-007": 753, "key-008": 832, "key-009": 621, "key-010": 519, "key-011": 407, "key-012": 905, "key-013": 132, "key-014": 658, "key-015": 294, "key-016": 745, "key-017": 389, "key-018": 910, "key-019": 482, "key-020": 371, "key-021": 648, "key-022": 573, "key-023": 781, "key-024": 452, "key-025": 390, "key-026": 167, "key-027": 296, "key-028": 854, "key-029": 731, "key-030": 513, "key-031": 249, "key-032": 675, "key-033": 890, "key-034": 412, "key-035": 567, "key-036": 712, "key-037": 361, "key-038": 284, "key-039": 946, "key-040": 709, "key-041": 541, "key-042": 673, "key-043": 325, "key-044": 498, "key-045": 823, "key-046": 654, "key-047": 832, "key-048": 276, "key-049": 792, "key-050": 619, "key-051": 485, "key-052": 527, "key-053": 831, "key-054": 491, "key-055": 350, "key-056": 764, "key-057": 539, "key-058": 204, "key-059": 926, "key-060": 687, "key-061": 498, "key-062": 143, "key-063": 359, "key-064": 871, "key-065": 604, "key-066": 318, "key-067": 425, "key-068": 691, "key-069": 536, "key-070": 174, "key-071": 523, "key-072": 680, "key-073": 352, "key-074": 870, "key-075": 429, "key-076": 237, "key-077": 491, "key-078": 391, "key-079": 702, "key-080": 826, "key-081": 318, "key-082": 563, "key-083": 496, "key-084": 791, "key-085": 142, "key-086": 380, "key-087": 943, "key-088": 467, "key-089": 389, "key-090": 905, "key-091": 281, "key-092": 478, "key-093": 654, "key-094": 193, "key-095": 849, "key-096": 740, "key-097": 268, "key-098": 431, "key-099": 739, "key-100": 511, "key-101": 234, "key-102": 593, "key-103": 800, "key-104": 137, "key-105": 405, "key-106": 872, "key-107": 364, "key-108": 230, "key-109": 793, "key-110": 649, "key-111": 507, "key-112": 391, "key-113": 170, "key-114": 923, "key-115": 478, "key-116": 375, "key-117": 682, "key-118": 195, "key-119": 735, "key-120": 341, "key-121": 263, "key-122": 498, "key-123": 149, "key-124": 517, "key-125": 350, "key-126": 630, "key-127": 809, "key-128": 472, "key-129": 367, "key-130": 953, "key-131": 284, "key-132": 576, "key-133": 395, "key-134": 719, "key-135": 364, "key-136": 157, "key-137": 861, "key-138": 495, "key-139": 267, "key-140": 436, "key-141": 513, "key-142": 722, "key-143": 184, "key-144": 637, "key-145": 912, "key-146": 501, "key-147": 294, "key-148": 178, "key-149": 843, "key-150": 671, }  func BenchmarkMySyncMap(b *testing.B) { m := NewSyncMap(len(data)) b.ResetTimer()  for i := 0; i < b.N; i++ { for k, v := range data { m.Store(k, v) }  for k, v := range data { v2, ok := m.Load(k) if !ok || v2 != v { b.Fatalf("key %s not found in cache (%v) or incorrect value: %v", k, ok, v2) } } } }  func BenchmarkGoSyncMap(b *testing.B) { var m sync.Map b.ResetTimer()  for i := 0; i < b.N; i++ { for k, v := range data { m.Store(k, v) }  for k, v := range data { v2, ok := m.Load(k) if !ok || v2 != v { b.Fatalf("key %s not found in cache (%v) or incorrect value: %v", k, ok, v2) } } } }  func BenchmarkMySyncMapParallel(b *testing.B) { m := NewSyncMap(150 * 2) b.ResetTimer()  b.RunParallel(func(pb *testing.PB) { for pb.Next() { for k, v := range data { m.Store(k, v) }  for k, v := range data { v2, ok := m.Load(k) if !ok || v2 != v { b.Fatalf("key %s not found in cache (%v) or incorrect value: %v", k, ok, v2) } } } }) }  func BenchmarkGoSyncMapParallel(b *testing.B) { var m sync.Map b.ResetTimer() b.RunParallel(func(pb *testing.PB) { for pb.Next() { for k, v := range data { m.Store(k, v) }  for k, v := range data { v2, ok := m.Load(k) if !ok || v2 != v { b.Fatalf("key %s not found in cache (%v) or incorrect value: %v", k, ok, v2) } } } }) }  func BenchmarkFastSyncMapWriteMillion(b *testing.B) { m := NewSyncMap(150 * 2) totalEntries := 1000000 b.ResetTimer()  b.RunParallel(func(pb *testing.PB) { for pb.Next() { for i := 0; i < totalEntries; i++ { key := strconv.Itoa(i) m.Store(key, i) m.Load(key) } } }) }  func BenchmarkSyncMapWriteMillion(b *testing.B) { var m sync.Map totalEntries := 1000000 b.ResetTimer()  b.RunParallel(func(pb *testing.PB) { for pb.Next() { for i := 0; i < totalEntries; i++ { key := strconv.Itoa(i) m.Store(key, i) m.Load(key) } } }) }

Результат выполнения бенчмарка на моем ПК

goos: linux goarch: amd64 pkg: lesson cpu: 12th Gen Intel(R) Core(TM) i7-12700K BenchmarkMySyncMap BenchmarkMySyncMap-20                      74986        15030 ns/op BenchmarkGoSyncMap BenchmarkGoSyncMap-20                      76708        15605 ns/op BenchmarkMySyncMapParallel BenchmarkMySyncMapParallel-20             479565         2518 ns/op BenchmarkGoSyncMapParallel BenchmarkGoSyncMapParallel-20             455433         2679 ns/op BenchmarkFastSyncMapWriteMillion BenchmarkFastSyncMapWriteMillion-20            4    264691361 ns/op BenchmarkSyncMapWriteMillion BenchmarkSyncMapWriteMillion-20                3    458739675 ns/op PASS

Здесь мы видим, что записи\чтении в одном потоке стандартная sync.Map выигрывает.
При конкурентном доступе с малой нагрузкой fast sync map быстрее на 2%.
При конкурентном доступе с нагрузкой в миллион записей fast sync map быстрее на 73%.

Данные моей тачки, где выполнялся бенчмарк:

$ lscpu Architecture:            x86_64   CPU op-mode(s):        32-bit, 64-bit   Address sizes:         46 bits physical, 48 bits virtual   Byte Order:            Little Endian CPU(s):                  20   On-line CPU(s) list:   0-19 Vendor ID:               GenuineIntel   Model name:            12th Gen Intel(R) Core(TM) i7-12700K     CPU family:          6     Model:               151     Thread(s) per core:  2     Core(s) per socket:  12     Socket(s):           1     Stepping:            2     CPU max MHz:         5000,0000     CPU min MHz:         800,0000     BogoMIPS:            7219.20     Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bt                          s rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt                           tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx                          2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 xsaves split_lock_detect avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window h                          wp_epp hwp_pkg_req hfi vnmi umip pku ospke waitpkg gfni vaes vpclmulqdq tme rdpid movdiri movdir64b fsrm md_clear serialize pconfig arch_lbr ibt flush_l1d arch_capabilities Virtualization features:    Virtualization:        VT-x Caches (sum of all):        L1d:                   512 KiB (12 instances)   L1i:                   512 KiB (12 instances)   L2:                    12 MiB (9 instances)   L3:                    25 MiB (1 instance) NUMA:                       NUMA node(s):          1   NUMA node0 CPU(s):     0-19 Vulnerabilities:            Gather data sampling:  Not affected   Itlb multihit:         Not affected   L1tf:                  Not affected   Mds:                   Not affected   Meltdown:              Not affected   Mmio stale data:       Not affected   Retbleed:              Not affected   Spec rstack overflow:  Not affected   Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl   Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization   Spectre v2:            Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S   Srbds:                 Not affected   Tsx async abort:       Not affected

sudo lshw -short -C memory H/W path           Device     Class          Description ======================================================== /0/0                          memory         64KiB BIOS /0/3b                         memory         40GiB System Memory /0/3b/0                       memory         8GiB DIMM Synchronous 4800 MHz (0,2 ns) /0/3b/1                       memory         16GiB DIMM Synchronous 4800 MHz (0,2 ns) /0/3b/2                       memory         16GiB DIMM Synchronous 4800 MHz (0,2 ns) /0/3b/3                       memory         [empty] /0/4b                         memory         384KiB L1 cache /0/4c                         memory         256KiB L1 cache /0/4d                         memory         10MiB L2 cache /0/4e                         memory         25MiB L3 cache /0/4f                         memory         128KiB L1 cache /0/50                         memory         256KiB L1 cache /0/51                         memory         2MiB L2 cache /0/52                         memory         25MiB L3 cache /0/100/14.2                   memory         RAM memory

Если мы заглянем в pprof memory profile, то получим результат:

sync.Map  Showing nodes accounting for 67752.28kB, 99.89% of 67827.20kB total       flat  flat%   sum%        cum   cum% 51064.96kB 75.29% 75.29% 54407.03kB 80.21%  sync.(*Map).Swap  6975.31kB 10.28% 85.57% 67752.34kB 99.89%  lesson.BenchmarkSyncMapWriteMillion.func1  6373.84kB  9.40% 94.97%  6373.84kB  9.40%  strconv.formatBits  3338.13kB  4.92% 99.89%  3338.13kB  4.92%  sync.newEntry (inline)  ====================================  Showing nodes accounting for 108636.43kB, 99.92% of 108720.77kB total       flat  flat%   sum%        cum   cum% 45864.58kB 42.19% 42.19% 75216.60kB 69.18%  sync.(*Map).Swap 23786.82kB 21.88% 64.06% 23786.82kB 21.88%  sync.(*Map).dirtyLocked 22013.31kB 20.25% 84.31% 22013.31kB 20.25%  strconv.formatBits 11164.25kB 10.27% 94.58% 86380.85kB 79.45%  lesson.(*FastSyncMap).Store  5561.55kB  5.12% 99.70%  5561.55kB  5.12%  sync.newEntry (inline)

FastSyncMap потребляет примерно в 1.6 раза больше памяти, чем sync.Map.

Получается, наша реализация обеспечивает лучшую производительность параллельных операций за счет увеличенного потребления памяти. Это компромисс между скоростью и использованием памяти, что может быть приемлемо в случаях, когда требуется высокая производительность и доступно достаточное количество оперативной памяти.

Идем дальше — смотрим CPU профиль

go tool pprof fastsyncmap_cpu.prof File: lesson.test Type: cpu Time: Jun 19, 2024 at 10:38am (MSK) Duration: 1s, Total samples = 3.10s (309.30%) Entering interactive mode (type "help" for commands, "o" for options) (pprof) top Showing nodes accounting for 2130ms, 68.71% of 3100ms total Dropped 52 nodes (cum <= 15.50ms) Showing top 10 nodes out of 80       flat  flat%   sum%        cum   cum%      440ms 14.19% 14.19%      560ms 18.06%  runtime.mapaccess2      300ms  9.68% 23.87%      300ms  9.68%  runtime.(*mspan).base (inline)      270ms  8.71% 32.58%      270ms  8.71%  runtime.(*gcBits).bitp (inline)      270ms  8.71% 41.29%      310ms 10.00%  runtime.findObject      210ms  6.77% 48.06%      210ms  6.77%  aeshashbody      190ms  6.13% 54.19%      190ms  6.13%  runtime.procyield      160ms  5.16% 59.35%     1380ms 44.52%  runtime.gcDrain      160ms  5.16% 64.52%     1190ms 38.39%  runtime.scanobject       70ms  2.26% 66.77%       70ms  2.26%  sync.(*entry).tryExpungeLocked       60ms  1.94% 68.71%       60ms  1.94%  runtime.(*mspan).heapBitsSmallForAddr               go tool pprof syncmap_cpu.profcpu.prof File: lesson.test Type: cpu Time: Jun 19, 2024 at 10:38am (MSK) Duration: 1.01s, Total samples = 2.13s (210.73%) Entering interactive mode (type "help" for commands, "o" for options) (pprof) top Showing nodes accounting for 1550ms, 72.77% of 2130ms total Dropped 47 nodes (cum <= 10.65ms) Showing top 10 nodes out of 56       flat  flat%   sum%        cum   cum%      280ms 13.15% 13.15%      380ms 17.84%  runtime.mapaccess2      270ms 12.68% 25.82%      270ms 12.68%  runtime.procyield      210ms  9.86% 35.68%      210ms  9.86%  runtime.(*mspan).base (inline)      190ms  8.92% 44.60%      190ms  8.92%  runtime.(*gcBits).bitp (inline)      140ms  6.57% 51.17%      150ms  7.04%  runtime.findObject      130ms  6.10% 57.28%      130ms  6.10%  aeshashbody      100ms  4.69% 61.97%      810ms 38.03%  runtime.scanobject       90ms  4.23% 66.20%      230ms 10.80%  runtime.mallocgc       80ms  3.76% 69.95%       80ms  3.76%  runtime.markBits.isMarked (inline)       60ms  2.82% 72.77%       60ms  2.82%  runtime.nextFreeFast (inline) 

• Общее время выполнения:

  • FastSyncMap использовал 3100ms CPU.

  • sync.Map использовал 2130ms CPU.

• Основные потребители CPU:

  • В обоих случаях значительное количество времени тратится на функцию runtime.mapaccess2, которая отвечает за доступ к элементам карты (sync.Map и, предположительно, внутренние структуры FastSyncMap).

• Гарbage Collection и управление памятью:

  • gcDrain и scanobject также занимают значительное время в обоих профилях, указывая на активное участие сборщика мусора (GC).

  • runtime.procyield и aeshashbody также занимают значительное время, что может указывать на задержки и вычисления, связанные с хешированием и управлением ресурсами.

Идем дальше — смотрим профиль блокировок

go tool pprof fastsyncmap_block.prof File: lesson.test Type: delay Time: Jun 19, 2024 at 10:40am (MSK) Entering interactive mode (type "help" for commands, "o" for options) (pprof) top Showing nodes accounting for 3122.65ms, 100% of 3122.65ms total Dropped 2 nodes (cum <= 15.61ms) Showing top 10 nodes out of 14       flat  flat%   sum%        cum   cum%  2076.23ms 66.49% 66.49%  2076.23ms 66.49%  sync.(*WaitGroup).Wait   703.08ms 22.52% 89.00%   703.08ms 22.52%  sync.(*Mutex).Lock (inline)   343.34ms 11.00%   100%   343.34ms 11.00%  runtime.chanrecv1          0     0%   100%   702.53ms 22.50%  lesson.(*FastSyncMap).Store          0     0%   100%  2419.57ms 77.48%  lesson.BenchmarkFastSyncMapWriteMillion          0     0%   100%   703.08ms 22.52%  lesson.BenchmarkFastSyncMapWriteMillion.func1          0     0%   100%   343.34ms 11.00%  runtime/pprof.StopCPUProfile          0     0%   100%   702.53ms 22.50%  sync.(*Map).Store (inline)          0     0%   100%   702.53ms 22.50%  sync.(*Map).Swap          0     0%   100%  2076.23ms 66.49%  testing.(*B).RunParallel   go tool pprof syncmap_block.prof  File: lesson.test Type: delay Time: Jun 19, 2024 at 10:40am (MSK) Entering interactive mode (type "help" for commands, "o" for options) (pprof) top Showing nodes accounting for 7777.40ms, 100% of 7777.40ms total Dropped 2 nodes (cum <= 38.89ms) Showing top 10 nodes out of 26       flat  flat%   sum%        cum   cum%  3550.66ms 45.65% 45.65%  3550.66ms 45.65%  sync.(*WaitGroup).Wait  3310.10ms 42.56% 88.21%  3310.10ms 42.56%  runtime.chanrecv1   916.65ms 11.79%   100%   916.65ms 11.79%  sync.(*Mutex).Lock (inline)          0     0%   100%   702.53ms  9.03%  lesson.(*FastSyncMap).Store          0     0%   100%  2609.71ms 33.56%  lesson.BenchmarkFastSyncMapWriteMillion          0     0%   100%   703.08ms  9.04%  lesson.BenchmarkFastSyncMapWriteMillion.func1          0     0%   100%  1626.74ms 20.92%  lesson.BenchmarkSyncMapWriteMillion          0     0%   100%   213.57ms  2.75%  lesson.BenchmarkSyncMapWriteMillion.func1          0     0%   100%  2624.31ms 33.74%  main.main          0     0%   100%  2624.31ms 33.74%  runtime.main 

Анализ результатов

1. Общее время задержек:

   • FastSyncMap: 3122.65 ms

   • sync.Map: 7777.40 ms

sync.Map имеет значительно большее общее время задержек по сравнению с FastSyncMap.

2. Основные узлы задержек:

   • В FastSyncMap основное время задержек приходится на sync.(*WaitGroup).Wait (66.49%) и sync.(*Mutex).Lock (22.52%).

   • В sync.Map основное время задержек также приходится на sync.(*WaitGroup).Wait (45.65%) и runtime.chanrecv1 (42.56%).

Объяснение

• Время ожидания WaitGroup:

  • Оба метода используют sync.WaitGroup для синхронизации горутин, что приводит к значительному времени ожидания. В FastSyncMap это время составляет 2076.23 ms (66.49%), в то время как в sync.Map это время составляет 3550.66 ms (45.65%).

• Время ожидания блокировок Mutex:

  • В FastSyncMap блокировки sync.Mutex вызывают задержки на 703.08 ms (22.52%), в то время как в sync.Map задержки из-за sync.Mutex составляют 916.65 ms (11.79%).

• Время ожидания каналов:

  • В sync.Map значительное время (3310.10 ms, 42.56%) уходит на ожидание в каналах, что может быть связано с особенностями реализации и конкурентным доступом к элементам карты.

Заключение

1. FastSyncMap:

   • Имеет меньшее общее время задержек (3122.65 ms) по сравнению с sync.Map.

   • Основные задержки связаны с sync.WaitGroup (66.49%) и sync.Mutex (22.52%).

2. sync.Map:

   • Имеет большее общее время задержек (7777.40 ms).

   • Основные задержки связаны с sync.WaitGroup (45.65%) и ожиданием в каналах (42.56%).