ComptimeStringMap: return a regular struct and optimize

[travisstaloch]

EDIT: note to readers - this commit message is old Please read the current, updated one.

this patch makes ComptimeStringMap accept only a single type parameter and return a known struct type instead of an anonymous struct. initial motivation for these changes was to reduce the 'very long type names' issue described here https://github.com/ziglang/zig/pull/19682.

this breaks the previous API. users will now need to write: const map = std.ComptimeStringMap(T).init(kvs_list);

• move kvs_list param from type param to an init() param
• adds new public convenience helpers keys() and values()
• adds new public methods which i'm not sure belong but have left in for now incase they are deemed useful.
  • getPartial(str), getIndexPartial(str), initRuntime(allocator), deinit(allocator)
  • includes test coverage for all
• performance notes:
  • i posted some benchmarking results here: https://github.com/travisstaloch/comptime-string-map-revised/issues/1
  • i noticed speedup reducing the size of the struct from 48 to 32 bytes and thus use u32s instead of usize for all length fields
  • i noticed speedup storing KVs as a struct of arrays
  • latest benchmark shows these wall_time improvements for debug/safe/small/fast builds: -6.6% / -10.2% / -19.1% / -8.9%. full poop output in link above.

[Vexu]

Could the name be changed while we're breaking the API? Instead of ComptimeStringMap with initRuntime have something like StaticStringMap with initComptime?

[travisstaloch]

sure no problem. will work on that now.

[travisstaloch]

should I leave in initRuntime()? if so, should I rename it to init() now?

[travisstaloch]

Could the name be changed while we're breaking the API? Instead of ComptimeStringMap with initRuntime have something like StaticStringMap with initComptime?

This is done. We'll see how many typos i made :smile:

[travisstaloch]

CI doesn't like that I've renamed lib/std/comptime_string_map.zig to lib/std/static_string_map.zig

ninja: error: '../lib/std/comptime_string_map.zig', needed by 'zig2.c', missing and no known rule to make it

[travisstaloch]

CI doesn't like that I've renamed lib/std/comptime_string_map.zig to lib/std/static_string_map.zig

For now, I've moved back to the original name so we can make progress.

[BratishkaErik]

CI doesn't like that I've renamed lib/std/comptime_string_map.zig to lib/std/static_string_map.zig

ninja: error: '../lib/std/comptime_string_map.zig', needed by 'zig2.c', missing and no known rule to make it

I think you need to also change this line (in samencommit), so that CMake knows this "dependency" is renamed: https://github.com/ziglang/zig/blob/3c5e840732053318f5e722d6cc16f65d51cdc297/CMakeLists.txt#L225

[travisstaloch]

I think you need to also change this line (in samencommit), so that CMake knows this "dependency" is renamed:

Thanks! Just pushed this change.

[Vexu]

if so, should I rename it to init() now?

That's what I was going for.

[travisstaloch]

Sounds good! Thats an easy change.

Also, any thoughts about whether I should remove getPartial()? I found it very useful for tokenizing or parsing to have a way to check if a string starts with any key from the map and thats why I've left it in. If it should stay, any idea of a better name than getPartial(str)? Something like getLongestKVAtStartOf(str)? I'm struggling with the name.

[erikarvstedt]

getMaxPrefix

/// Returns the key-value pair for the longest key that is a prefix of str.

[travisstaloch]

getMaxPrefix

Not bad. I think I'd prefer getLongestPrefix() :thinking:

[travisstaloch]

That's what I was going for.

@Vexu done - renamed initRuntime() to init(). Also renamed getPartial() to getLongestPrefix() and cleaned up tests and documentation a little more. I removed most of the duplicated testing of runtime init(), leaving only a couple. So the tests look a lot more like they did before this PR.

[travisstaloch]

Perf point: building my simdjzon project with around 7000 loc zig files in src folder.

Note that I'm not super confident in my process so here are some notes:

• zig below is a release build i built yesterday (../build-release/stage3/bin/zig) and is available in $PATH.
• ../zig/stage4/bin/zig was built with ../build-release/stage3/bin/zig build -p stage4 -Denable-llvm -Dno-lib -Doptimize=ReleaseFast.

.../zig/simdjzon $ zig version
0.13.0-dev.8+c352845e8
.../zig/simdjzon $ ../zig/stage4/bin/zig version
0.13.0-dev.9+21a3a5710
.../zig/simdjzon $ poop 'zig build-exe -fno-emit-bin -ODebug --dep simdjzon -Mroot=src/main.zig --dep build_options -Msimdjzon=src/simdjzon.zig -Mbuild_options=zig-cache/c/8caf24ab22f7fa50f13c4c948a6b8cca/options.zig --cache-dir zig-cache --global-cache-dir /home/travis/.cache/zig --name simdjzon' '../zig/stage4/bin/zig build-exe -fno-emit-bin -ODebug --dep simdjzon -Mroot=src/main.zig --dep build_options -Msimdjzon=src/simdjzon.zig -Mbuild_options=zig-cache/c/8caf24ab22f7fa50f13c4c948a6b8cca/options.zig --cache-dir zig-cache --global-cache-dir /home/travis/.cache/zig --name simdjzon'
Benchmark 1 (36 runs): zig build-exe -fno-emit-bin -ODebug --dep simdjzon -Mroot=src/main.zig --dep build_options -Msimdjzon=src/simdjzon.zig -Mbuild_options=zig-cache/c/8caf24ab22f7fa50f13c4c948a6b8cca/options.zig --cache-dir zig-cache --global-cache-dir /home/travis/.cache/zig --name simdjzon
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           139ms ± 1.58ms     136ms …  144ms          1 ( 3%)        0%
  peak_rss            111MB ±  285KB     111MB …  112MB          1 ( 3%)        0%
  cpu_cycles          619M  ± 3.32M      612M  …  626M           4 (11%)        0%
  instructions        986M  ± 4.88K      986M  …  986M           2 ( 6%)        0%
  cache_references   58.8M  ±  356K     58.1M  … 59.5M           0 ( 0%)        0%
  cache_misses       8.02M  ±  106K     7.85M  … 8.24M           0 ( 0%)        0%
  branch_misses      4.60M  ± 28.0K     4.54M  … 4.68M           1 ( 3%)        0%
Benchmark 2 (41 runs): ../zig/stage4/bin/zig build-exe -fno-emit-bin -ODebug --dep simdjzon -Mroot=src/main.zig --dep build_options -Msimdjzon=src/simdjzon.zig -Mbuild_options=zig-cache/c/8caf24ab22f7fa50f13c4c948a6b8cca/options.zig --cache-dir zig-cache --global-cache-dir /home/travis/.cache/zig --name simdjzon
  measurement          mean ± σ            min … max           outliers         delta
  wall_time           123ms ± 1.24ms     121ms …  128ms          1 ( 2%)        ⚡- 11.5% ±  0.5%
  peak_rss            106MB ±  178KB     106MB …  106MB          2 ( 5%)        ⚡-  4.5% ±  0.1%
  cpu_cycles          465M  ± 3.15M      461M  …  479M           2 ( 5%)        ⚡- 24.8% ±  0.2%
  instructions        718M  ± 4.03K      718M  …  718M           0 ( 0%)        ⚡- 27.1% ±  0.0%
  cache_references   52.7M  ±  342K     52.1M  … 53.5M           0 ( 0%)        ⚡- 10.4% ±  0.3%
  cache_misses       7.56M  ±  133K     7.30M  … 7.96M           2 ( 5%)        ⚡-  5.8% ±  0.7%
  branch_misses      3.13M  ± 19.2K     3.08M  … 3.18M           3 ( 7%)        ⚡- 31.9% ±  0.2%

This seems too good to be true. Can anyone spot any mistakes or maybe try reproducing with this branch and building a different project?

[travisstaloch]

Perf point: building my simdjzon project with around 7000 loc zig files in src folder.

I got some feedback on discord from @jacobly0 @nektro and @Sinon (sorry forget your github handle).

if you want to benchmark code speed it's better to do it at runtime in a loop in an executable and benchmark the executable

The consensus I think is that this benchmark isn't reliable since there are too many moving parts such as caching. So I believe my previous benchmarks are a better measurement.

[andrewrk]

EDIT: note to readers - this commit message is old Please read the current, updated one.

Can you edit your PR description to be correct so that I can use it for release notes in the future?

nice work, btw.

[travisstaloch]

Can you edit your PR description to be correct so that I can use it for release notes in the future?

Thanks! Done. And will do.