aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_map.c
AgeCommit message (Collapse)Author
2015-08-31Merge branch 'maint'Sverker Eriksson
2015-08-28erts: Fix hipe bug for maps:merge/2Sverker Eriksson
Add forgotten HIPE_WRAPPER_BIF_DISABLE_GC which could lead to stack-heap overrun if unlucky with the yielding during maps:merge when called by native hipe code.
2015-06-24erts: Remove halfword heap relative comparisionsBjörn-Egil Dahlberg
* Removed cmp_rel, cmp_rel_term and eq_rel
2015-06-24erts: Remove halfword basic relative heap operationsBjörn-Egil Dahlberg
2015-06-24erts: Remove HALFWORD_HEAP definitionBjörn-Egil Dahlberg
2015-06-18Change license text to APLv2Bruce Yinhe
2015-06-15Merge branch 'hamt_bin2term'Sverker Eriksson
* 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
2015-06-15erts: Remove hashmap probabilistic heap overestimationSverker Eriksson
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.
2015-06-15erts: Optimize maps:mergeSverker Eriksson
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.
2015-06-15erts: Yield in maps:mergeSverker Eriksson
2015-06-08erts: Refactor arg swapping for maps:mergeSverker Eriksson
2015-05-11Merge branch 'egil/fix-maps-copy-shallow'Björn-Egil Dahlberg
* 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
2015-05-08erts: Fix erts_debug:size/1 for large MapsBjörn-Egil Dahlberg
2015-05-08erts: Make hashmap_get halfword safeBjörn-Egil Dahlberg
2015-04-16Merge branch 'egil/maps-refactor'Björn-Egil Dahlberg
* egil/maps-refactor: erts: Use make_small for size terms on flat maps Conflicts: erts/emulator/beam/erl_bif_guard.c
2015-04-15Raise more descriptive error messages for failed map operationsBjörn Gustavsson
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.
2015-04-14erts: Use make_small for size terms on flat mapsBjörn-Egil Dahlberg
2015-04-10Merge branch 'egil/fix-maps-deep-colliding-merge'Björn-Egil Dahlberg
* egil/fix-maps-deep-colliding-merge: erts: Fix deep colliding hash values in maps:from_list/1
2015-04-09Merge branch 'sverk/maps-bin2term-eqhash-bug/12585'Sverker Eriksson
* 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
2015-04-08Merge branch 'sverk/refactor-encode-size/OTP-12585'Sverker Eriksson
* 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
2015-04-07erts: Fix bug in map_from_list when keys clash in both value and hashSverker Eriksson
Subtle bug in qsort callback. Cast from Sint to int does not retain sign.
2015-04-07erts: Fix bug in binary_to_term for big maps with 32 bit hash-clashSverker Eriksson
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.
2015-04-07erts: Fix deep colliding hash values in maps:from_list/1Björn-Egil Dahlberg
Reported-by: Jesper Louis Andersen
2015-04-01Merge branch 'egil/fix-maps-tmp-heap'Björn-Egil Dahlberg
* 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
2015-03-31erts: Use halfword secure tmp heapBjörn-Egil Dahlberg
2015-03-31erts: Fix size bug in maps:from_list/1 BIFBjörn-Egil Dahlberg
The wrong size was imprinted on maps with deep hash key collisions.
2015-03-31erts: Optimize insert and delete for big mapsSverker Eriksson
Do fast path without bit count for full internal nodes.
2015-03-25erts: Refactor Map - use multiple values ESTACK_PUSHNBjörn-Egil Dahlberg
2015-03-25erts: GC needs the size even if the frag is not referencedBjörn-Egil Dahlberg
2015-03-25erts: Combine flat and hash maps under one unifying tagBjörn-Egil Dahlberg
2015-03-25Merge branch 'sverk/hamt-term2bin-bug/OTP-12585'Sverker Eriksson
* 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
2015-03-25Merge branch 'maint'Björn-Egil Dahlberg
Conflicts: erts/emulator/beam/erl_map.c erts/emulator/test/map_SUITE.erl
2015-03-24erts: Optimize hashmap_getSverker Eriksson
2015-03-24erts: Remove HAMT_SUBTAG_NODE_ARRAYSverker Eriksson
This will also fix a bug in term_to_binary treating full nodes as tuples and emiting LIST_EXT for leafs.
2015-03-24erts: Fix comparison of exact termsBjörn-Egil Dahlberg
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
2015-03-23erts: Rename to flatmap_from_validated_listSverker Eriksson
from map_to_validated_list
2015-03-20erts: Fix hashmap overestimationSverker Eriksson
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.
2015-03-19erts: Ensure maps uses _rel functions in halfwordBjörn-Egil Dahlberg
2015-03-19erts: Ensure halfword has correct temp-heap for mapsBjörn-Egil Dahlberg
2015-03-13erts: Restrict GCC intrinsics by compiler versionBjörn-Egil Dahlberg
Intrinsics __builtin_clz and __builtin_popcount are only valid on GCC version 3.4 and above.
2015-03-12erts: Fix windows bug in hashmap_infoSverker Eriksson
undefined symbol 'MAX'
2015-03-12erts: Make hashmap iterator more flexibleSverker Eriksson
to allow mixing of 'next' and 'prev' operations.
2015-03-12erts, kernel: Fix erts_debug:size/1 for hashmapsBjörn-Egil Dahlberg
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.
2015-03-12erts: Reintroduce is_map macroSverker Eriksson
as shorthand for is_flatmap || is_hashmap
2015-03-12erts: Refactor maps naming conventionSverker Eriksson
flatmap: Small map hashmap: Large map map: flatmap or hashmap
2015-03-12erts: Add hashmap_iterator_prev to mapsBjörn-Egil Dahlberg
2015-03-12erts: Tweak over estimation of hashmap size for binary_to_termSverker Eriksson
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?)
2015-03-12erts: Reject duplicate keys for hamt in binary_to_termSverker Eriksson
2015-03-12First stab at binary_to_term for hamtSverker Eriksson
with over estimation of heap size.
2015-03-12erts: Fix various map vs hamt size bugsSverker Eriksson