aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_map.c
AgeCommit message (Collapse)Author
2019-02-06Merge tag 'OTP-21.2' into sverker/map-from-ks-vs-bugSverker Eriksson
2019-02-06erts: Fix bug in erts_map_from_ks_and_vsSverker Eriksson
This sleeping bug was introduced in OTP 19.1 but not possible not provoke until OTP 21.0 when enif_make_map_from_arrays was introduced.
2018-06-18Update copyright yearHenrik Nord
2018-05-16erts: Silence gcc warningsSverker Eriksson
‘res’ may be used uninitialized in this function
2018-05-09erts: Try fix contant maps:next orderSverker Eriksson
Symptom: maps:iterator+next returns different orders for the exact same map. Problem: Number of cached key-values within iterator term depends on number of input reductions to erts_internal_map_next_3. Solution: Build cached key-values in destructive non-reverse order to not affect iteration order.
2018-04-29Introduce is_map_key/2 guard BIFMichał Muskała
This complements the `map_get/2` guard BIF introduced in #1784. Rationale. `map_get/2` allows accessing map fields in guards, but it might be problematic in more complex guard expressions, for example: foo(X) when map_get(a, X) =:= 1 or is_list(X) -> ... The `is_list/1` part of the guard could never succeed since the `map_get/2` guard would fail the whole guard expression. In this situation, this could be solved by using `;` instead of `or` to separate the guards, but it is not possible in every case. To solve this situation, this PR proposes a `is_map_key/2` guard that allows to check if a map has key inside a guard before trying to access that key. When combined with `is_map/1` this allows to construct a purely boolean guard expression testing a value of a key in a map. Implementation. Given the use case motivating the introduction of this function, the PR contains compiler optimisations that produce optimial code for the following guard expression: foo(X) when is_map(X) and is_map_key(a, X) and map_get(a, X) =:= 1 -> ok; foo(_) -> error. Given all three tests share the failure label, the `is_map_key/2` and `is_map/2` tests are optimised away. As with `map_get/2` the `is_map_key/2` BIF is allowed in match specs.
2018-04-24Introduce map_get guard-safe functionMichał Muskała
Rationale Today all compound data types except for maps can be deconstructed in guards. For tuples we have `element/2` and for lists `hd/1` and `tl/1`. Maps are completely opaque to guards. This means matching on maps can't be abstracted into macros, which is often done with repetitive guards. It also means that maps have to be always selected whole from ETS tables, even when only one field would be enough, which creates a potential efficiency issue. This PR introduces an `erlang:map_get/2` guard-safe function that allows extracting a map field in guard. An alternative to this function would be to introduce the syntax for extracting a value from a map that was planned in the original EEP: `Map#{Key}`. Even outside of guards, since this function is a guard-BIF it is more efficient than using `maps:get/2` (since it does not need to set up the stack), and more convenient from pattern matching on the map (compare: `#{key := Value} = Map, Value` to `map_get(key, Map)`). Performance considerations A common concern against adding this function is the notion that "guards have to be fast" and ideally execute in constant time. While there are some counterexamples (`length/1`), what is more important is the fact that adding those functions does not change in any way the time complexity of pattern matching - it's already possible to match on map fields today directly in patterns - adding this ability to guards will niether slow down or speed up the execution, it will only make certain programs more convenient to write. This first version is very naive and does not perform any optimizations.
2018-03-23Add enif_make_map_from_arraysJohn Högberg
2017-11-20erts: Limit size of first iterator for hashmapsLukas Larsson
2017-11-20erts: Remove erts_internal:maps_to_list/2Lukas Larsson
This function is no longer needed as maps:iterator has now been implemented.
2017-11-20erts: Implement batching maps:iteratorLukas Larsson
This iterator implementation fetches multiple elements to iterate over in one call to erts_internal:maps_next instead of one at a time. This means that the memory usage will go up for the iterator as we are buffering elements, but the usage is still bounded. In this implementation the max memory usage is 1000 words. Using this approach makes the iterator as fast as using maps:to_list, so maps:iterator/2 has been removed.
2017-10-13erts: Implement maps path iteratorLukas Larsson
2017-10-13erts: Implement map iterator using a stackLukas Larsson
This version does not work great as the subtrees created are not proper hash maps. Also it is not all that performant as the extra allocations to keep the stack there is expensive.
2017-05-04Update copyright yearRaimo Niskanen
2017-02-23erts: Introduce erts_internal:maps_to_list/2Björn-Egil Dahlberg
2017-02-14erts: Add deallocation veto for magic destructorsSverker Eriksson
A magic destructor can return 0 and thereby take control and prolong the lifetime of a magic binary.
2017-02-06Use magic refs for maps merge trap contextRickard Green
2016-07-14erts: Add erts_map_from_ks_and_vsLukas Larsson
2016-04-22erts: Add BIF maps:take/2Björn-Egil Dahlberg
2016-04-13Merge branch 'henrik/update-copyrightyear'Henrik Nord
* henrik/update-copyrightyear: update copyright-year
2016-04-01erts: Don't search for non-existing Map keys twiceBjörn-Egil Dahlberg
* For maps:get/2,3 and maps:find/2, searching for an immediate key, e.g. an atom, the search was performed twice if the key did not exist in the map.
2016-03-15update copyright-yearHenrik Nord
2016-02-24Merge branch 'master' into sverk/master/halt-INT_MINSverker Eriksson
2016-02-24erts: Change erl_exit into erts_exitSverker Eriksson
This is mostly a pure refactoring. Except for the buggy cases when calling erlang:halt() with a positive integer in the range -(INT_MIN+2) to -INT_MIN that got confused with ERTS_ABORT_EXIT, ERTS_DUMP_EXIT and ERTS_INTR_EXIT. Outcome OLD erl_exit(n, ) NEW erts_exit(n, ) ------- ------------------- ------------------------------------------- exit(Status) n = -Status <= 0 n = Status >= 0 crashdump+abort n > 0, ignore n n = ERTS_ERROR_EXIT < 0 The outcome of the old ERTS_ABORT_EXIT, ERTS_INTR_EXIT and ERTS_DUMP_EXIT are the same as before (even though their values have changed).
2015-12-07erts: Let term_type/1 encompass all typesBjörn-Egil Dahlberg
2015-12-07erts: Change erts_internal:map_type/1 into term_type/1Sverker Eriksson
to support other terms, not just maps
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