| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
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.
|
|
Summary: This commit simplifies the implementation of the "GC BIFs" so
that they no longer need to do a garbage collection, removing duplicate
code for all GC BIFs in the runtime system, as well as potentially
reducing the size of the loaded BEAM code by using shorter
instructions calling those BIFs.
A GC BIF is a guard BIF that will do a garbage
collection if it needs to build anything on the heap.
For example, `abs/1` is a GC BIF because it might need to
allocate space on the heap (if the result is a floating point
number or the resulting integer is a bignum).
Before R12, a guard BIF (such as `abs/1`) that need to allocate
heap space would allocate outside of process's main heap, in
a heap fragment.
GC BIFs were introduced in R12B to support literals. During garbage
collection it become necessary to quickly test whether a term was
a literal. To make the check simple, guards BIFs were no longer
allowed to create heap fragments. Instead GC BIFs were introduced.
In OTP 19, the implementation of literals was changed to support
storing messages in heap fragments outside of the main heap for a
process. That change again made it allowed for guard BIFs to create
heap fragments when they need to build terms on the heap.
It would even be possible for the guard BIFs to build directly
on the main heap if there is room there, because the compiler
assumes that a new `test_heap/2` instruction must be emitted
when building anything after calling a GC BIF. (We don't do that
in this commit; see below.)
This commit simplifies the implementation of the GC BIFs in
the runtime system.
Each GC BIF had a dual implementation: one that was used when the GC
BIF was called directly and one used when it was called via
`apply/3`. For example, `abs/1` was implemented in `abs_1()` and
`erts_gc_abs_1()`. This commit removes the GC version of each BIF. The
other version that allocates heap space using `HAlloc()` is updated to
use the new `HeapFragOnlyAlloc()` macro that will allocate heap
space in a heap fragment outside of the main heap.
Because the BIFs will allocate outside of the main heap, the same
`bif` instructions used by nonbuilding BIFs can be used for the
(former) GC BIFs. Those instructions don't use the macros that save
and restore the heap and stack pointers (SWAPOUT/SWAPIN). If the
former GC BIFs would build on the main heap, either new instructions
would be needed, or SWAPOUT/SWAPIN instructions would need to be added
to the `bif` instructions.
Instructions that call the former GC BIFs don't need the operand
that specifies the number of live X registers. Therefore, the
instructions that call the BIFs are usually one word shorter.
|
|
This patch optimizes map operations to not allocate new maps
when the key is being replaced by the exact same value in memory.
Imagine this very common idiom:
Map#{key := compute_new_value(Value, Condition)}
where:
compute_new_x(X, true) -> X + 1;
compute_new_x(X, false) -> X;
In many cases, we are not changing the value in `Key`, however
the code prior to this patch would still allocate a new array
for the map values. This optimization changes this.
The cost of optimization is minimum, as in the worst case scenario
it only adds a pointer comparison and boolean check. The major benefit
is reducing the GC pressure by avoiding allocating data.
Next we list the operations we have changed alongside the benchmark
results. The benchmarks basically create a map and perform the same
operations, roughly 20000 times, once replacing the key with the same
value, and another with a different value.
* Map#{Key := Value}
For a map with 4 keys, replacing the fourth key 20000 times went from
718us to 539us.
For a map with 8 keys, replacing the fourth key 20000 times went from
976us to 555us.
* maps:update/3
For a map with 4 keys, replacing the fourth key 20000 times went from
673us to 575us.
For a map with 8 keys, replacing the fourth key 20000 times went from
827us to 585us.
* maps:put/3
For a map with 4 keys, replacing the fourth key 20000 times went from
763us to 553us.
For a map with 8 keys, replacing the fourth key 20000 times went from
788us to 561us.
Note that we have ported some optimizations found in maps:update/3
to maps:put/3 while creating this patch.
|
|
Implementing it in Erlang allows taking advantage of the literal pool
optimisation, this means the function implemented in Erlang does no
allocations, while the BIF had to allocate new map each time it was
called. Benchmarks show the function is also slightly faster now.
|
|
|
|
‘res’ may be used uninitialized in this function
|
|
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.
|
|
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.
|
|
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.
|
|
|
|
|
|
This function is no longer needed as maps:iterator has
now been implemented.
|
|
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.
|
|
|
|
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.
|
|
|
|
|
|
A magic destructor can return 0 and thereby take control
and prolong the lifetime of a magic binary.
|
|
|
|
|
|
|
|
* henrik/update-copyrightyear:
update copyright-year
|
|
* 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.
|
|
|
|
|
|
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).
|
|
|
|
to support other terms, not just maps
|
|
|
|
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.
|
|
* Removed cmp_rel, cmp_rel_term and eq_rel
|
|
|
|
|
|
|
|
* 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
|
