Skip to content

runtime: map cold cache improvements #70835

Closed
Closed
runtime: map cold cache improvements#70835
Assignees
prattmic
Labels
NeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.Performancecompiler/runtimeIssues related to the Go compiler and/or runtime.
Milestone
Go1.28

Description

@prattmic
prattmic
opened on Dec 13, 2024

There is room for improvement when some or all of a map is not in cache. The hierarchical design we use to enable incremental growth leaves us with several different allocations that can experience cache misses:

  1. The Map itself (on m.Used)
  2. The directory slice (on m.directoryAt)
  3. The table (on t.groups.lengthMask)
  4. The control word (on matchH2)
  5. The slot key (on key comparison)
  6. The slot value (on access in the caller)

(4), (5), and (6) are in the same object, so they may share a cache line depending on how far apart they are.

Some changes that may help (or may make things worse!):

  • Grouping control words together (prototype).
    • Good for locality of control words. Probably most useful for lookup of keys that aren't in the map (as the key has worse locality with the control word).
    • Also good for optimistic prefetch of the first control word, something that Abseil does.
  • Change the directory from []*table to []table (prototype).
    • Effectively merges cases (2) and (3).
  • Store group data directly in the table. The table becomes variable size, with a table8 containing 1 group, table16 containing 2 groups, and so on up to table1024.
    • Effectively merges cases (3) and (4).
    • Allows optimistic prefetch of the control word / first key before even touching the table as they are at fixed offsets.
    • We'd likely want to store the size in the directory as well to enable above.
    • This is unfortunately mutually exclusive with the previous option, as the table is variable-sized.

There is also the question of whether to store the key and value together (KVKVKV...), as we do today, or to group the keys together (KKKVVV...), as we do in the old maps. Both cases have pros and cons:

K/V together:

  • Map hit
    • Cache miss on control word
    • Cache miss on key comparison
    • No cache miss on value use in parent
  • Map miss
    • Cache miss on control word
    • Cache miss on key comparison in false positive matches (~1%)
    • No value

All keys together:

  • Map hit
    • Cache miss on control word
    • No cache miss on key comparison
    • Cache miss on value use in parent (if used)
  • Map miss
    • Cache miss on control word
    • No cache miss on key comparison in false positive matches (~1%)
    • No value

Activity

  1. prattmic
    added
    Performance
    NeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.
    on Dec 13, 2024
  2. prattmic
    added this to the Go1.25 milestone on Dec 13, 2024
  3. prattmic
    self-assigned this
    on Dec 13, 2024
  4. prattmic
    added this to Go Compiler / Runtime / Commandon Dec 13, 2024
  5. gopherbot
    added
    compiler/runtimeIssues related to the Go compiler and/or runtime.
    on Dec 13, 2024

  6. gabyhelp commented on Dec 13, 2024

    @gabyhelp
    gabyhelp
    on Dec 13, 2024

    Related Issues

    Related Code Changes

    (Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)

  7. mknyszek
    moved this to Todo in Go Compiler / Runtime / Commandon Dec 18, 2024

  8. bboreham commented on Apr 16, 2025

    @bboreham
    bboreham
    on Apr 16, 2025
    Contributor

    I noticed Prometheus uses more CPU using Go 1.24, in a couple of places where it is accessing a large map.

    This was hard to see with existing benchmarks, so I modified this benchmark to generate more data (and stripped out extra test cases to make it easier to run).

    Check out that branch and run like this:

    go test -run XXX -bench 'BenchmarkLoadWLs' -cpuprofile=cpu.pprof ./tsdb/
goos: linux
goarch: amd64
pkg: github.com/prometheus/prometheus/tsdb
cpu: Intel(R) Core(TM) i7-14700K
BenchmarkLoadWLs/batches=1000,seriesPerBatch=10000,samplesPerSeries=50,exemplarsPerSeries=0,mmappedChunkT=0,oooSeriesPct=0.000,oooSamplesPct=0.000,oooCapMax=0,missingSeriesPct=0.000-28                       1        25232921108 ns/op
PASS
ok      github.com/prometheus/prometheus/tsdb   33.909s

    Using Go 1.23 I get 82 seconds of CPU in runtime.mapaccess1_fast64; with Go 1.24.2 it's 108 seconds.

    Profile from the latter:
    cpu.pprof.gz

    [Gnarly extra info: Prometheus shards this map 16,000 ways by default, to reduce lock contention. But when I change that number down to 128 this benchmark still looks much the same.]

  9. gopherbot
    modified the milestones: Go1.25, Go1.26 on Aug 12, 2025

  10. gopherbot commented on Oct 14, 2025

    @gopherbot
    gopherbot
    on Oct 14, 2025
    Contributor

    Change https://go.dev/cl/711560 mentions this issue: internal/runtime/maps: use KKKKVVVV slot order

  11. randall77
    modified the milestones: Go1.26, Go1.27 on Dec 30, 2025

  12. gopherbot commented on Mar 24, 2026

    @gopherbot
    gopherbot
    on Mar 24, 2026
    Contributor

    Change https://go.dev/cl/758760 mentions this issue: main.star: add mapsplitgroup builder

  13. gopherbot
    added 2 commits that reference this issue on Mar 24, 2026

    internal/runtime/maps: add GOEXPERIMENT=mapsplitgroup for KKKKVVVV sl…

    5560073

    main.star: add mapsplitgroup builder

    250d81f

  14. prattmic commented on Mar 24, 2026

    @prattmic
    prattmic
    on Mar 24, 2026
    MemberAuthor

    https://go.dev/cl/711560 adds GOEXPERIMENT=mapsplitgroup, switching to the "All keys together" variant described above. My intention is to evaluate performance on several production workloads to determine if the change is neutral or better (neutral is OK because #71368 is improved). Hopefully we can decide whether to commit to this before the 1.27 freeze.

  15. gopherbot
    modified the milestones: Go1.27, Go1.28 on Aug 19, 2026

  16. prattmic commented on Aug 24, 2026

    @prattmic
    prattmic
    on Aug 24, 2026
    MemberAuthor

    I've (finally) completed an analysis of GOEXPERIMENT=mapsplitgroup on Google production workloads, and found it was neutral on cache effects: no change to IPC or LLC cache misses. Given the reduced padding in the memory layout is an improvement, I think this is worth enabling by default.

  17. gopherbot commented on Aug 24, 2026

    @gopherbot
    gopherbot
    on Aug 24, 2026
    Contributor

    Change https://go.dev/cl/820500 mentions this issue: internal/buildcfg: enable GOEXPERIMENT=mapsplitgroup by default

  18. gopherbot
    added a commit that references this issue on Aug 24, 2026

    internal/buildcfg: enable GOEXPERIMENT=mapsplitgroup by default

    26c2ec0
  19. prattmic
    closed this as completedon Sep 28, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

NeedsInvestigationSomeone must examine and confirm this is a valid issue and not a duplicate of an existing one.Performancecompiler/runtimeIssues related to the Go compiler and/or runtime.

Type

No type

Projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions