| Age | Commit message (Collapse) | Author |
|---|
|
# Conflicts:
# erts/emulator/beam/erl_db_tree.c
|
|
* sverker/erts/ets-select_replace-bug/OTP-15346:
erts: Fix bug in ets:select_replace for bound key
|
|
which may cause following calls to ets:next or ets:prev to fail.
|
|
meta_wb
smp_insert
smp_fixed_delete
smp_select_delete
|
|
to reduce test times
|
|
Avoid repeating same tests for [] and [set].
Test case 'default' verifies 'set' to be the default type.
|
|
by populating the table with the help of a random number generator
creating series of unique integers.
|
|
of repeated table opts
and waiting for workers
|
|
The current ETS ordered_set implementation can quickly become a
scalability bottleneck on multicore machines when an application updates
an ordered_set table from concurrent processes [1][2]. The current
implementation is based on an AVL tree protected from concurrent writes
by a single readers-writer lock. Furthermore, the current implementation
has an optimization, called the stack optimization [3], that can improve
the performance when only a single process accesses a table but can
cause bad scalability even in read-only scenarios. It is possible to
pass the option {write_concurrency, true} to ets:new/2 when creating an
ETS table of type ordered_set but this option has no effect for tables
of type ordered_set without this commit. The new ETS ordered_set
implementation, added by this commit, is only activated when one passes
the options ordered_set and {write_concurrency, true} to the ets:new/2
function. Thus, the previous ordered_set implementation (from here on
called the default implementation) can still be used in applications
that do not benefit from the new implementation. The benchmark results
on the following web page show that the new implementation is many times
faster than the old implementation in some scenarios and that the old
implementation is still better than the new implementation in some
scenarios.
http://winsh.me/ets_catree_benchmark/ets_ca_tree_benchmark_results.html
The new implementation is expected to scale better than the default
implementation when concurrent processes use the following ETS
operations to operate on a table:
delete/2, delete_object/2, first/1, insert/2 (single object),
insert_new/2 (single object), lookup/2, lookup_element/2, member/2,
next/2, take/2 and update_element/3 (single object).
Currently, the new implementation does not have scalable support for the
other operations (e.g., select/2). However, when these operations are
used infrequently, the new implantation may still scale better than the
default implementation as the benchmark results at the URL above shows.
Description of the New Implementation
----------------------------------
The new implementation is based on a data structure which is called the
contention adapting search tree (CA tree for short). The following
publication contains a detailed description of the CA tree:
A Contention Adapting Approach to Concurrent Ordered Sets
Journal of Parallel and Distributed Computing, 2018
Kjell Winblad and Konstantinos Sagonas
https://doi.org/10.1016/j.jpdc.2017.11.007
http://www.it.uu.se/research/group/languages/software/ca_tree/catree_proofs.pdf
A discussion of how the CA tree can be used as an ETS back-end can be
found in another publication [1]. The CA tree is a data structure that
dynamically changes its synchronization granularity based on detected
contention. Internally, the CA tree uses instances of a sequential data
structure to store items. The CA tree implementation contained in this
commit uses the same AVL tree implementation as is used for the default
ordered set implementation. This AVL tree implementation is reused so
that much of the existing code to implement the ETS operations can be
reused.
Tests
-----
The ETS tests in `lib/stdlib/test/ets_SUITE.erl` have been extended to
also test the new ordered_set implementation. The function
ets_SUITE:throughput_benchmark/0 has also been added to this file. This
function can be used to measure and compare the performance of the
different ETS table types and options. This function writes benchmark
data to standard output that can be visualized by the HTML page
`lib/stdlib/test/ets_SUITE_data/visualize_throughput.html`.
[1]
More Scalable Ordered Set for ETS Using Adaptation.
In Thirteenth ACM SIGPLAN workshop on Erlang (2014).
Kjell Winblad and Konstantinos Sagonas.
https://doi.org/10.1145/2633448.2633455
http://www.it.uu.se/research/group/languages/software/ca_tree/erlang_paper.pdf
[2]
On the Scalability of the Erlang Term Storage
In Twelfth ACM SIGPLAN workshop on Erlang (2013)
Kjell Winblad, David Klaftenegger and Konstantinos Sagonas
https://doi.org/10.1145/2505305.2505308
http://winsh.me/papers/erlang_workshop_2013.pdf
[3]
The stack optimization works by keeping one preallocated stack instance
in every ordered_set table. This stack is updated so that it contains
the search path in some read operations (e.g., ets:next/2). This makes
it possible for a subsequent ets:next/2 to avoid traversing some nodes
in some cases. Unfortunately, the preallocated stack needs to be flagged
so that it is not updated concurrently by several threads which cause
bad scalability.
|
|
|
|
causing erlang:memory to report too much ets memory.
|
|
|
|
|
|
|
|
by using a cooperative strategy that will make
any process accessing the table execute delelete_all_objects_continue
until the table is empty.
This is not an optimal solution as concurrent threads will still
block on the table lock, but at least thread progress is made.
|
|
and not the name. For more sane named table semantics.
Applies to both select/1 continuation and trap context.
|
|
Communication between Erlang processes has conceptually always been
performed through asynchronous signaling. The runtime system
implementation has however previously preformed most operation
synchronously. In a system with only one true thread of execution, this
is not problematic (often the opposite). In a system with multiple threads
of execution (as current runtime system implementation with SMP support)
it becomes problematic. This since it often involves locking of structures
when updating them which in turn cause resource contention. Utilizing
true asynchronous communication often avoids these resource contention
issues.
The case that triggered this change was contention on the link lock due
to frequent updates of the monitor trees during communication with a
frequently used server. The signal order delivery guarantees of the
language makes it hard to change the implementation of only some signals
to use true asynchronous signaling. Therefore the implementations
of (almost) all signals have been changed.
Currently the following signals have been implemented as true
asynchronous signals:
- Message signals
- Exit signals
- Monitor signals
- Demonitor signals
- Monitor triggered signals (DOWN, CHANGE, etc)
- Link signals
- Unlink signals
- Group leader signals
All of the above already defined as asynchronous signals in the
language. The implementation of messages signals was quite
asynchronous to begin with, but had quite strict delivery constraints
due to the ordering guarantees of signals between a pair of processes.
The previously used message queue partitioned into two halves has been
replaced by a more general signal queue partitioned into three parts
that service all kinds of signals. More details regarding the signal
queue can be found in comments in the erl_proc_sig_queue.h file.
The monitor and link implementations have also been completely replaced
in order to fit the new asynchronous signaling implementation as good
as possible. More details regarding the new monitor and link
implementations can be found in the erl_monitor_link.h file.
|
|
|
|
into 'sverker/master/alloc-n-migration/ERIERL-88'
|
|
into 'sverker/maint-20/alloc-n-migration/ERIERL-88'
OTP-14915
OTP-14916
OTP-14917
OTP-14918
|
|
as memory stats do not guarantee consistency.
A typical ETS test case ends by a lot of deallocating
that may now trigger homecoming carrier migration,
that in turn can cause quite large inconsistencies
in memory stats when same carrier is accounted for twice
or not at all.
And that's my theory why I now sometimes see transient discrepancies
between before and after memory stats.
|
|
The efile driver will soon be reimplemented as a BIF.
Instead of opening a port based on efile, use hd(erlang:ports()). It
is a reasonable safe assumption that the runtime will continue to use
use at least some ports.
|
|
|
|
|
|
* sverker/ets-select-replace-const:
stdlib: Add examples for ets:select_replace docs
erts: Fix ets:select_replace with {const, NewTuple}
|
|
Enable ets:select_replace to do a generic single object
compare-and-swap operation of any ets-tuple using
a matchspec like this:
[{Old, [], [{const, New}]}]
The only exception when this does not work is if the key
contains maps or atoms looking like variables (like '$1').
|
|
|
|
to run 3*3 seconds to avoid timeout on slow machines.
|
|
|
|
run_workers/* -> run_smp_workers/*
run_workers_do/4 -> run_sched_workers/4
|
|
|
|
|
|
Preemptively fail operation with badarg if the replacement object
might have a different key.
|
|
The existing implementation presented both
semantic inconsistencies and performance issues.
|
|
|
|
and let each test case fail, like it was before.
Seems growing/shrinking meta tables was causing the sporadic
failed memory checks.
|
|
from process psd through all owned/fixed tables.
As meta_pid_to{_fixed}_tab maps to slot in meta_main_tab
which is planned for destruction.
In this commit we no longer seize table lock while
freeing the table (free_table_cont) as it's not needed
and makes the code a bit simpler. Any concurrent operation
on the table will only access lock, owner and status
and then bail out.
|
|
|
|
In the future we will run xref to make sure that all functions
that are exported are also used. Having internal exports only
used for spawning or applying will mess with that.
|
|
|
|
* valgrind needs lots of time
|
|
* rickard/time-unit/OTP-13831:
Replace usage of deprecated time units
|
|
|
|
no point in checking table load as select_delete does
not shrink.
|
|
by simply asking for the size of struct ext_segtab
|
|
due to the grow/shrink hysteresis of the meta tables
|
|
for faster lookup/insert/delete
at the expense of about one word per object.
|
|
|
|
|
|
This reverts commit 7c133fb1094ad1cabbb5cfc157483a43c816c6a9.
|
