search

shapesecurity / shape-functional-java

add some FP familiarity to a Java project
Apache License 2.0
8 stars 7 forks source link

Track hashcode for ImmutableList, version 2.5.3 #65

Closed Protryon closed 5 years ago

Protryon commented 5 years ago

Removes hashCode caching in place of gradual calculation to reduce massive recursion when calculating an uncached hashCode for long lists. Caching is done implicitly.

Contains version bump, rebase not squash.

michaelficarra commented 5 years ago

Another approach we could use is to set some recursion depth constant, skip entries until the length is under that constant (pushing onto the stack every time we skip that many), do the regular recursive calculation, then "step backward" via the stack and repeat. Does that make sense? We'd basically be batching the work.

Protryon commented 5 years ago

@michaelficarra Yes, that approach would work, but then we get the non-trivial performance penalty for recursion and the added complexity, along with more state tracking.

michaelficarra commented 5 years ago

Then we should measure the perf and pick the better one.

Protryon commented 5 years ago

@michaelficarra Current PR performance for calculating hashCode of 100000 Integers: 11.553387001156807 ms Master branch with recursion: Stack Overflow

In implementation of your idea, there doesn't seem to be a good way to implement it without a breaking change of function headers. We would need to pass data to/from calcHashCode, which is a protected method, and therefore external children might depend on it having a certain prototype. Furthermore, I see no possible way that recursion could be more performant than iteration in this case.

EDIT: Performance data for hashCode of 2500 integer entries (5000 is stack overflow on master): Master: 1.582657 ms This branch: 1.192556 ms