diff options
| author | John Högberg <[email protected]> | 2018-10-15 18:17:12 +0200 |
|---|---|---|
| committer | Lukas Larsson <[email protected]> | 2018-11-02 17:15:32 +0100 |
| commit | bf5886b790f8f386ed425f543506a4bebb48448c (patch) | |
| tree | b2ef444c7bc5fc21b9e1e4cf905041ca70832c78 /erts/emulator/beam/erl_alloc.types | |
| parent | db6059a9217767a6e42e93cec05089c0ec977d20 (diff) | |
| download | otp-bf5886b790f8f386ed425f543506a4bebb48448c.tar.gz otp-bf5886b790f8f386ed425f543506a4bebb48448c.tar.bz2 otp-bf5886b790f8f386ed425f543506a4bebb48448c.zip | |
Optimize operator '--' and yield on large inputs
The removal set now uses a red-black tree instead of an array on
large inputs, decreasing runtime complexity from `n*n` to
`n*log(n)`. It will also exit early when there are no more items
left in the removal set, drastically improving performance and
memory use when the items to be removed are present near the head
of the list.
This got a lot more complicated than before as the overhead of
always using a red-black tree was unacceptable when either of the
inputs were small, but this compromise has okay-to-decent
performance regardless of input size.
Co-authored-by: Dmytro Lytovchenko <[email protected]>
Diffstat (limited to 'erts/emulator/beam/erl_alloc.types')
| -rw-r--r-- | erts/emulator/beam/erl_alloc.types | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_alloc.types b/erts/emulator/beam/erl_alloc.types index 252bf1cc7e..af1133b853 100644 --- a/erts/emulator/beam/erl_alloc.types +++ b/erts/emulator/beam/erl_alloc.types @@ -322,6 +322,7 @@ type THR_PRGR_DATA LONG_LIVED SYSTEM thr_prgr_data type T_THR_PRGR_DATA SHORT_LIVED SYSTEM temp_thr_prgr_data type RELEASE_LAREA SHORT_LIVED SYSTEM release_literal_area +endif +type LIST_TRAP SHORT_LIVED PROCESSES list_bif_trap_state # # Types used for special emulators |