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

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

Задача была написать аналог 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.

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

Диаграмма использования памяти sync.Map

Диаграмма использования памяти Fast 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)

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

• Основные потребители 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.

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

   • В 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%).

© Habrahabr.ru