| Age | Commit message (Collapse) | Author |
|---|
|
|
|
to easier generate a routing tree for test
without having to spend cpu to provoke actual repeated lock conflicts.
|
|
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.
|
|
|
|
as it's now only used for empty tables by ets:new/2.
|
|
|
|
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.
|
|
|
|
Cannot read fix->counter safely without table lock.
|
|
|
|
This refactor was done using the unifdef tool like this:
for file in $(find erts/ -name *.[ch]); do unifdef -t -f defile -o $file $file; done
where defile contained:
#define ERTS_SMP 1
#define USE_THREADS 1
#define DDLL_SMP 1
#define ERTS_HAVE_SMP_EMU 1
#define SMP 1
#define ERL_BITS_REENTRANT 1
#define ERTS_USE_ASYNC_READY_Q 1
#define FDBLOCK 1
#undef ERTS_POLL_NEED_ASYNC_INTERRUPT_SUPPORT
#define ERTS_POLL_ASYNC_INTERRUPT_SUPPORT 0
#define ERTS_POLL_USE_WAKEUP_PIPE 1
#define ERTS_POLL_USE_UPDATE_REQUESTS_QUEUE 1
#undef ERTS_HAVE_PLAIN_EMU
#undef ERTS_SIGNAL_STATE
|
|
|
|
to replace macro ERTS_INTERNAL_BINARY_FIELDS
as header in Binary and friends.
|
|
|
|
Preemptively fail operation with badarg if the replacement object
might have a different key.
|
|
|
|
|
|
|
|
'the_name' keeps name of all tables.
'type' & DB_NAMED_TABLE mark tables as named.
table ref id is built from magic bin when needed.
|
|
\o/
O
/ \
Also removed the body for CHECK_TABLES enabled by HARDDEBUG.
Removed quite useless check for hash,
but kept dead check code for tree.
|
|
to get rid of meta table lookup by integer (tb->common.id)
|
|
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.
|
|
|
|
|
|
|
|
A magic destructor can return 0 and thereby take control
and prolong the lifetime of a magic binary.
|
|
|
|
NIF resources was not handled in a thread-safe manner in the runtime
system without SMP support.
As a consequence of this fix, the following driver functions are now
thread-safe also in the runtime system without SMP support:
- driver_free_binary()
- driver_realloc_binary()
- driver_binary_get_refc()
- driver_binary_inc_refc()
- driver_binary_dec_refc()
|
|
Instead of passing around a file descriptor
use a function pointer to facilitate more advanced
backend write logic such as size limitation or compression.
|
|
in 'set' with 'write_concurrency'
when inserting default object causes table to grow
and the bucket to split is protected by same lock as the key.
|
|
and non-call-trace.
This is the easy way out to avoid difficult locking
scenarios when accessing tracing flags on another process.
|
|
|
|
|
|
* maint:
Introduce time management in native APIs
Introduce time warp safe replacement for safe_fixed option
Introduce time warp safe trace timestamp formats
Conflicts:
erts/emulator/beam/erl_bif_trace.c
erts/emulator/beam/erl_driver.h
erts/emulator/beam/erl_nif.h
erts/emulator/beam/erl_trace.c
erts/preloaded/ebin/erlang.beam
|
|
The new time warp safe option is safe_fixed_monotonic_time which
gives erlang:monotonic_time().
The safe_fixed option was also slightly changed. It now gives
erlang:timestamp() instead of erlang:now(). This has however
not been documented, so it is considered a compatible change.
The above effects both ets, and dets.
This commit also include the bugfix OTP-13239 for
dets:info(Tab, safe_fixed). The timestamp in the result returned
by dets:info(Tab, safe_fixed) was unintentionally broken as a
result of the time API rewrites in OTP 18.0.
|
|
|
|
* Remove macros size_object_rel, copy_struct_rel and copy_shallow_rel
|
|
* Removed cmp_rel, cmp_rel_term and eq_rel
|
|
|
|
|
|
|
|
The optimization cannot be used due to that the pattern cannot be ordered.
|
|
Conflicts:
erts/emulator/beam/bif.tab
lib/stdlib/src/ets.erl
|
|
This new ETS BIF returns and deletes objects from tables.
|
|
|
|
|
|
|
|
Functionality for scheduling operations at thread progress later
has been introduced.
Deallocation of ETS table structures were previously done by scheduling
misc aux work. Deallocation of process structures (not released yet)
was also implemented this way. Instead of using the misc aux work
functionality these implementation now use the newly introduced
functionality for scheduling operations at thread progress later. By
using this new functionaliy we reduce the amount of memory
allocation/deallocation operations needed.
|
|
|
|
As a preparation for changing the calling convention for
BIFs, make sure that all BIFs use the macros. Also, eliminate
all calls from one BIF to another, since that also breaks
the calling convention abstraction.
|
