Age | Commit message (Collapse) | Author |
|
|
|
|
|
* hamt_bin2term:
erts: Add erts_factory_trim_and_close
erts: Optimize driver_deliver_term
erts: Remove hashmap probabilistic heap overestimation
Conflicts:
erts/emulator/beam/beam_load.c
|
|
by adding a dynamic heap factory.
"binary_to_term" is now a hybrid solution with both
a call to decoded_size() to calculate needed heap space
AND possible dynamic allocation of more heap space
if needed for big maps.
The heap size returned from decoded_size() is guaranteed
to be sufficient for all term heap data except for hashmap
nodes. All hashmap nodes are created at the end of dec_term()
by invoking the heap factory interface that may allocate more
heap space on process heap or in fragments.
With this commit it is no longer guaranteed that a message
is confined to only one heap fragment.
|
|
to be better at reusing entire hashmap sub-trees.
Sub-tree reuse is detected in three cases:
1. The sub-tree top node does not exist at all in the other map.
Already implemented before this commit.
2. The exact same sub-tree exist in both maps.
Must calculate nr of keys in tree to get total size right.
3. We detect that a sub-tree only contains stuff from one of the maps.
There is still one case we don't detect. If A and B leafs have equal
keys we could also compare the values. If values are equal, further
node reuse could propagate up toward the root (by 'mix'==0).
The downside would be potentially expensive value comparisons.
|
|
|
|
|
|
* egil/fix-maps-copy-shallow:
erts: Make hashmap_get halfword safe
erts: Fix ETS db_has_variable check for large Maps
stdlib: Strengthen ETS Maps tests
erts: Fix copy shallow for large Maps
stdlib: Strengthen ETS Maps tests
erts: ETS ordered_set cannot use it's optimization with Maps
stdlib: Strengthen ETS Maps tests
stdlib: Refactor away ?line macro
|
|
|
|
|
|
* egil/maps-refactor:
erts: Use make_small for size terms on flat maps
Conflicts:
erts/emulator/beam/erl_bif_guard.c
|
|
According to EEP-43 for maps, a 'badmap' exception should be
generated when an attempt is made to update non-map term such as:
<<>>#{a=>42}
That was not implemented in the OTP 17.
José Valim suggested that we should take the opportunity to
improve the errors coming from map operations:
http://erlang.org/pipermail/erlang-questions/2015-February/083588.html
This commit implement better errors from map operations similar
to his suggestion.
When a map update operation (Map#{...}) or a BIF that expects a map
is given a non-map term, the exception will be:
{badmap,Term}
This kind of exception is similar to the {badfun,Term} exception
from operations that expect a fun.
When a map operation requires a key that is not present in a map,
the following exception will be raised:
{badkey,Key}
José Valim suggested that the exception should be
{badkey,Key,Map}. We decided not to do that because the map
could potentially be huge and cause problems if the error
propagated through links to other processes.
For BIFs, it could be argued that the exceptions could be simply
'badmap' and 'badkey', because the bad map and bad key can be found in
the argument list for the BIF in the stack backtrace. However, for the
map update operation (Map#{...}), the bad map or bad key will not be
included in the stack backtrace, so that information must be included
in the exception reason itself. For consistency, the BIFs should raise
the same exceptions as update operation.
If more than one key is missing, it is undefined which of
keys that will be reported in the {badkey,Key} exception.
|
|
|
|
* egil/fix-maps-deep-colliding-merge:
erts: Fix deep colliding hash values in maps:from_list/1
|
|
* sverk/maps-bin2term-eqhash-bug/12585:
erts: Fix bug in map_from_list when keys clash in both value and hash
erts: Fix bug in binary_to_term for big maps with 32 bit hash-clash
|
|
* sverk/refactor-encode-size/OTP-12585:
erts: Optimize insert and delete for big maps
erts: Optimize == and /= for unequal big maps
erts: Refactor encode_size_struct_int
Conflicts:
erts/emulator/beam/erl_map.c
|
|
Subtle bug in qsort callback. Cast from Sint to int does not retain sign.
|
|
binary_to_term threw badarg as the "reject_dupkey" case in
hashmap_from_unsored_array was always triggered when hash-clash was
found as the first round in the loop compared the key with itself.
|
|
Reported-by: Jesper Louis Andersen
|
|
* egil/fix-maps-tmp-heap:
erts: Test deep Maps updates
erts: Use halfword secure tmp heap
erts: Remove unused tmp heap in make_internal_hash
Conflicts:
erts/emulator/test/map_SUITE.erl
|
|
|
|
The wrong size was imprinted on maps with deep hash key collisions.
|
|
Do fast path without bit count for full internal nodes.
|
|
|
|
|
|
|
|
* sverk/hamt-term2bin-bug/OTP-12585:
erts: Optimize hashmap_get
erts: Remove HAMT_SUBTAG_NODE_ARRAY
erts: Fix bug in binary_to_term for hamt when yielding
erts: Rename to flatmap_from_validated_list
|
|
Conflicts:
erts/emulator/beam/erl_map.c
erts/emulator/test/map_SUITE.erl
|
|
|
|
This will also fix a bug in term_to_binary
treating full nodes as tuples and emiting LIST_EXT for leafs.
|
|
Comparison of exact terms could cause faulty term tests.
This was caused by a faulty (too small) internal type.
Symptom:
-1 = erts_internal:cmp_term(2147483648,0). %% wrong
Correct:
1 = erts_internal:cmp_term(2147483648,0).
Reported-by: Jesper Louis Andersen
|
|
from map_to_validated_list
|
|
Old overestimation assumed an average of k/3 nodes.
This can be bad for large maps (with tight standard deviations)
as the average vary between 0.3*k and up to almost 0.4*k.
|
|
|
|
|
|
Intrinsics __builtin_clz and __builtin_popcount are only valid on
GCC version 3.4 and above.
|
|
undefined symbol 'MAX'
|
|
to allow mixing of 'next' and 'prev' operations.
|
|
This commit introduces two BIFs:
* erts_internal:map_type/1
* erts_internal:map_hashmap_children/1
erts_internal:map_hashmap_children/1 is only intended for use within
erts_debug:size/1 since the internal hashmap node is not allowed to
leak anywhere.
|
|
as shorthand for is_flatmap || is_hashmap
|
|
flatmap: Small map
hashmap: Large map
map: flatmap or hashmap
|
|
|
|
Strategy: Calculate an over estimation of heap size that will give
such a low probability for overflow, that "it will not happen".
Scary assumption 1: Uniformly distributed hash values.
Scary assumption 2: Tree size is normally distributed (right?)
|
|
|
|
with over estimation of heap size.
|
|
|
|
|
|
Use extra key and value if needed.
|
|
Did not build a hashmap once the small limit was exceeded.
|
|
Maps should become hashmaps when merged size exceeds small limit size.
|