diff options
author | John Högberg <[email protected]> | 2018-10-15 18:17:12 +0200 |
---|---|---|
committer | John Högberg <[email protected]> | 2018-10-29 08:10:55 +0100 |
commit | eb9ee88f4cc640065f4902e270d834bfb596d5fc (patch) | |
tree | a7ca57899b6d52417900eedd12995183f54f3bd5 /erts/emulator/beam/erl_alloc.types | |
parent | 1056d2d1fd49f669a2001f03890e13c9cba76c1e (diff) | |
download | otp-eb9ee88f4cc640065f4902e270d834bfb596d5fc.tar.gz otp-eb9ee88f4cc640065f4902e270d834bfb596d5fc.tar.bz2 otp-eb9ee88f4cc640065f4902e270d834bfb596d5fc.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 5409b89bab..98ba0e5f07 100644 --- a/erts/emulator/beam/erl_alloc.types +++ b/erts/emulator/beam/erl_alloc.types @@ -274,6 +274,7 @@ type ML_YIELD_STATE SHORT_LIVED SYSTEM monitor_link_yield_state type ML_DIST STANDARD SYSTEM monitor_link_dist type PF3_ARGS SHORT_LIVED PROCESSES process_flag_3_arguments type SETUP_CONN_ARG SHORT_LIVED PROCESSES setup_connection_argument +type LIST_TRAP SHORT_LIVED PROCESSES list_bif_trap_state type ENVIRONMENT SYSTEM SYSTEM environment |