Skip to content

Treeify SAHashMap#14

Open
marschall wants to merge 1 commit intoObjectLayout:masterfrom
marschall:treeify-samap
Open

Treeify SAHashMap#14
marschall wants to merge 1 commit intoObjectLayout:masterfrom
marschall:treeify-samap

Conversation

@marschall
Copy link
Contributor

SAHashMap isn't quite a port of HashMap to StructuredArray. While
HashMap overflows to a red–black tree SAHashMap does not. This makes
performance comparisons problematic since different code is tested.

Directly porting HashMap to StructuredArray is not possible since the
table in HashMap is heterogeneous but needs to be homogeneous for
StructuredArray. The compromise implemented in this change is to store
the red–black tree in the next node instead of the node in the table.

This commit includes the following changes:

  • sync code based on JDK 8u92, also includes indentation
  • store a red–black tree in the next node if there are too many
    overflows
  • remove the sentinel flag on Node, use a sentinel object in the key
    due to padding this should save two words per entry and bring memory
    consumption in line with HashMap
    this may help performance
  • HashIterator, KeySpliterator, ValueSpliterator, EntrySpliterator were
    missing a few sentinel checks
  • SAAbstractMap seems kinda pointless but was left it in and synched

Unfortunately the code could use more testing in the areas of tree
corner cases and streams.

SAHashMap isn't quite a port of HashMap to StructuredArray. While
HashMap overflows to a red–black tree SAHashMap does not. This makes
performance comparisons problematic since different code is tested.

Directly porting HashMap to StructuredArray is not possible since the
table in HashMap is heterogeneous but needs to be homogeneous for
StructuredArray. The compromise implemented in this change is to store
the red–black tree in the next node instead of the node in the table.

This commit includes the following changes:

- sync code based on JDK 8u92, also includes indentation
- store a red–black tree in the next node if there are too many
  overflows
- remove the sentinel flag on Node, use a sentinel object in the key
  due to padding this should save two words per entry and bring memory
  consumption in line with HashMap
  this may help performance
- HashIterator, KeySpliterator, ValueSpliterator, EntrySpliterator were
  missing a few sentinel checks
- SAAbstractMap seems kinda pointless but was left it in and synched

Unfortunately the code could use more testing in the areas of tree
corner cases and streams.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant