aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/test/ets_SUITE.erl
AgeCommit message (Collapse)Author
2018-11-20stdlib: Fix bug in ets_SUITE:smp_ordered_iterationSverker Eriksson
Did fail on really slow unlucky machines.
2018-11-16erts: Fix offheap leak of ets catree tmp iteration keySverker Eriksson
Also fix erts_debug:get_internal_status(node_and_dist_references) for catree to also search route node keys for offheap stuff.
2018-11-01erts: Fix bug for catree iterationSverker Eriksson
with keys containing off-heap terms. The passed key may actually be the one already saved (if nodes have been joined), in which case we do nothing. Calling destroy_route_key() may destroy off-heap data.
2018-10-30stdlib: Add ets_SUITE:smp_ordered_iterationSverker Eriksson
to provoke iteration over a moving ordered_set with write_concurrency and make sure we hit all "stable" keys.
2018-10-30stdlib: Improve stim_cat_ord_set in ets_SUITESverker Eriksson
to generate a routing tree with keys that fit each test case.
2018-10-26erts: Join empty base nodes in catreeSverker Eriksson
The original implementation did not do this due to fear of bad performance. But we think the negative effect of "leaking" empty base nodes is more important to fix. To get the bad performance a special kind of access patterns is needed where base nodes are frequently emptied and then repopulated soon again. ets_SUITE:throughput_benchmark for example did not show any negative effect from this commit at all.
2018-10-23erts: Provoke random catree split/join for DEBUG emulatorSverker Eriksson
2018-10-23erts: Do contention adaptions during (updating) iterationsSverker Eriksson
Once an iteration key has been found, never fall back to first/last key in next/prev tree as trees may split or join under our feet. I.e we must always use previous key when searching for the next key.
2018-10-23stdlib: Optimize ets_SUITE:stimulate_contentionSverker Eriksson
with ets_force_split
2018-10-23erts: Implement ets:info(T, stats) for catreesSverker Eriksson
{RouteNodes, BaseNodes, MaxRouteTreeDepth}
2018-10-09Merge branch 'maint'Sverker Eriksson
# Conflicts: # erts/emulator/beam/erl_db_tree.c
2018-10-09Merge branch 'sverker/erts/ets-select_replace-bug/OTP-15346' into maintSverker Eriksson
* sverker/erts/ets-select_replace-bug/OTP-15346: erts: Fix bug in ets:select_replace for bound key
2018-10-09erts: Fix bug in ets:select_replace for bound keySverker Eriksson
which may cause following calls to ets:next or ets:prev to fail.
2018-09-28ets_SUITE: Remove more redundant option combosSverker Eriksson
meta_wb smp_insert smp_fixed_delete smp_select_delete
2018-09-24ets_SUITE: Try avoid redundant option combosSverker Eriksson
to reduce test times
2018-09-24ets_SUITE: Reduce table type combos by removing "void"Sverker Eriksson
Avoid repeating same tests for [] and [set]. Test case 'default' verifies 'set' to be the default type.
2018-09-21ets_SUITE: Optimize throughput_benchmarkSverker Eriksson
by populating the table with the help of a random number generator creating series of unique integers.
2018-09-05stdlib: Suppress test log spam in ets_SUITESverker Eriksson
of repeated table opts and waiting for workers
2018-09-05Add a more scalable ETS ordered_set implementationKjell Winblad
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.
2018-09-05Merge branch 'maint'Sverker Eriksson
2018-09-03erts: Fix ets memstat false leak of FixedDeletionSverker Eriksson
causing erlang:memory to report too much ets memory.
2018-06-28Remove ad-hoc memory use calculations in testsJohn Högberg
2018-06-18Update copyright yearHenrik Nord
2018-06-04erts: Reduce test log noise from ets_SUITESverker Eriksson
2018-05-08erts: Make atomic ets:delete_all_objects yieldSverker Eriksson
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.
2018-04-20erts: Use table ref for select continuationSverker Eriksson
and not the name. For more sane named table semantics. Applies to both select/1 continuation and trap context.
2018-03-21Implementation of true asynchronous signaling between processesRickard Green
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.
2018-02-22Add ets:whereis/1 for resolving table names -> tid()John Högberg
2018-02-12Merge 'sverker/maint-20/alloc-n-migration/ERIERL-88'Sverker Eriksson
into 'sverker/master/alloc-n-migration/ERIERL-88'
2018-02-12Merge 'sverker/maint-19/alloc-n-migration/ERIERL-88'Sverker Eriksson
into 'sverker/maint-20/alloc-n-migration/ERIERL-88' OTP-14915 OTP-14916 OTP-14917 OTP-14918
2017-12-20stdlib: Make ets_SUITE memory check try againSverker Eriksson
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.
2017-11-17Avoid using the efile driver in test suitesBjörn Gustavsson
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.
2017-11-06Fix typo in test/ets_SUITE.erlDimitris Zorbas
2017-07-17Fix testcases after removal of non-smp emulatorLukas Larsson
2017-05-10Merge branch 'sverker/ets-select-replace-const'Sverker Eriksson
* sverker/ets-select-replace-const: stdlib: Add examples for ets:select_replace docs erts: Fix ets:select_replace with {const, NewTuple}
2017-05-10erts: Fix ets:select_replace with {const, NewTuple}Sverker Eriksson
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').
2017-05-04Update copyright yearRaimo Niskanen
2017-04-04stdlib: Limit ets_SUITE:smp_select_replaceSverker Eriksson
to run 3*3 seconds to avoid timeout on slow machines.
2017-04-03stdlib: Skip ets_SUITE:otp_9423 for single sched smpSverker Eriksson
2017-04-03stdlib: Rename ets_SUITE:run_workersSverker Eriksson
run_workers/* -> run_smp_workers/* run_workers_do/4 -> run_sched_workers/4
2017-03-24Fix double hit bug of select/3 with bound keySverker Eriksson
2017-03-22Add more complete key-safety checkSverker Eriksson
2017-03-22Reject unsafe matchspecs on ets:select_replace/2Guilherme Andrade
Preemptively fail operation with badarg if the replacement object might have a different key.
2017-03-22Disable ets:select_replace/2 for bagsGuilherme Andrade
The existing implementation presented both semantic inconsistencies and performance issues.
2017-03-22Add unit tests for ets:select_replace/2Guilherme Andrade
2017-03-22stdlib: Remove ets_SUITE:memory_check_summarySverker Eriksson
and let each test case fail, like it was before. Seems growing/shrinking meta tables was causing the sporadic failed memory checks.
2017-03-22erts: Replace meta_pid_to{_fixed}_tab with linked listsSverker Eriksson
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.
2017-03-02Implement ets:all() using scheduler specific dataRickard Green
2017-02-10ets_SUITE: Eliminate internal exports used for spawn/applyBjörn Gustavsson
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.
2016-11-07Merge branch 'maint'Björn-Egil Dahlberg