Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(242)

Issue 7304099: runtime: Improve the map implementation.

Can't Edit
Can't Publish+Mail
Start Review
Created:
13 years, 8 months ago by khr
Modified:
13 years, 8 months ago
Reviewers:
Visibility:
Public.

Description

runtime: Improve the map implementation. New version is somewhat faster and use somewhat less memory. Mapping is done in two stages: 1) mapping from the hash value to a dense range of cell IDs. 2) mapping from dense range of cell IDs to key/value pairs. Keeping the key/value pairs in a separate, growable-array structure makes the iteration semantics easy. The implementation of #1 can then ignore iteration and just go for fast/dense encoding. Experiments put lookup at ~20% faster and insert at about 50% faster. Also uses slightly less memory. First bug-free version.

Patch Set 1 #

Patch Set 2 : diff -r 0bf8fba16ea2 https://code.google.com/p/go/ #

Patch Set 3 : diff -r 988d73fb1a18 https://code.google.com/p/go/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+909 lines, -816 lines) Patch
M src/cmd/gc/range.c View 1 3 chunks +2 lines, -3 lines 0 comments Download
M src/cmd/ld/dwarf.c View 1 1 chunk +1 line, -0 lines 0 comments Download
M src/pkg/runtime/hashmap.h View 1 2 2 chunks +23 lines, -28 lines 0 comments Download
M src/pkg/runtime/hashmap.c View 1 2 11 chunks +883 lines, -784 lines 0 comments Download
M src/pkg/runtime/runtime.h View 1 2 1 chunk +0 lines, -1 line 0 comments Download

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b