Clojure

Unrolled small maps

Details

  • Type: Feature Feature
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: Release 1.6
  • Fix Version/s: None
  • Component/s: None
  • Labels:

Description

Placeholder for unrolled small maps enhancement (companion for vectors at CLJ-1517).

Activity

Hide
Andy Fingerhut added a comment -

Is there an expectation that these would perform better that PersistentArrayMap?

Show
Andy Fingerhut added a comment - Is there an expectation that these would perform better that PersistentArrayMap?
Hide
Zach Tellman added a comment - - edited

Yes, in some cases significantly so, for three reasons (in rough order of importance):

  • positional constructors, without any need for array instantiation/population
  • short-circuiting equality checks using hash comparisons
  • no iteration on any operation

There are a series of benchmarks at https://github.com/ztellman/cambrian-collections/blob/master/test/cambrian_collections/map_test.clj#L64-L148, which compare operations against maps with both keywords (which don't benefit from the hash comparisons) and symbols (which do). The 7-entry map cases cause the unrolled maps to overflow, so they only exist to test the overflow mechanism.

I've run the benchmark suite on my laptop, and the results are at https://gist.github.com/ztellman/961001e1a77e4f76ee1d. Some notable results:

The rest of the benchmarks are marginally faster due to unrolling, but most of the performance benefits are from the above behaviors. In a less synthetic benchmark, I found that Cheshire JSON decoding (which is 33% JSON lexing and 66% data structure building) was sped up roughly 30-40%.

Show
Zach Tellman added a comment - - edited Yes, in some cases significantly so, for three reasons (in rough order of importance):
  • positional constructors, without any need for array instantiation/population
  • short-circuiting equality checks using hash comparisons
  • no iteration on any operation
There are a series of benchmarks at https://github.com/ztellman/cambrian-collections/blob/master/test/cambrian_collections/map_test.clj#L64-L148, which compare operations against maps with both keywords (which don't benefit from the hash comparisons) and symbols (which do). The 7-entry map cases cause the unrolled maps to overflow, so they only exist to test the overflow mechanism. I've run the benchmark suite on my laptop, and the results are at https://gist.github.com/ztellman/961001e1a77e4f76ee1d. Some notable results: The rest of the benchmarks are marginally faster due to unrolling, but most of the performance benefits are from the above behaviors. In a less synthetic benchmark, I found that Cheshire JSON decoding (which is 33% JSON lexing and 66% data structure building) was sped up roughly 30-40%.

People

Vote (10)
Watch (7)

Dates

  • Created:
    Updated: