aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib
AgeCommit message (Collapse)Author
2018-09-25Merge branch 'maint'Henrik Nord
2018-09-24Prepare releaseErlang/OTP
2018-09-21Merge PR-1952 from kjellwinblad/ca_tree_pull_requestSverker Eriksson
Add a more scalable ETS ordered_set implementation
2018-09-21Merge branch 'maint'Henrik Nord
2018-09-21Update copyright yearHenrik Nord
2018-09-19Merge branch 'raimo/stdlib/gen_statem-cleanup'Raimo Niskanen
OTP-14737 * raimo/stdlib/gen_statem-cleanup: Improve user's guide on time-outs Clean up and optimize code and doc
2018-09-18Merge pull request #1857 from RaimoNiskanen/raimo/rand-crypto-xoroshiro928Raimo Niskanen
OTP-14461 - New 'rand' algorithm: Xoroshiro928** also for 'crypto' Implement a new 'rand' algorithm named 'exro928ss' and a new 'crypto' plugin for 'rand' named 'crypto_aes'. Both are based on Xoroshiro928** which is derived from Xoroshiro1024** modified to use 58-bit words for performance reasons in the Erlang VM. Xoroshiro1024** has got the Xoroshiro1024 generator and the StarStar scrambler from the 2018 paper "Scrambled Linear Pseudorandom Number Generators" by David Blackman and Sebastiano Vigna. This generator and scrambler combination shows no systematic weaknesses in standard statistical tests as TestU01(BigCrush) and PractRand, unlike the previously used * and + scramblers in the 'rand' module that exhibit statistical weaknesses for the lowest bits. The 'crypto' plugin uses AES-256 as scrambler and the Xoroshiro928 as generator, which gives the same very long period and jump functions as for Xoroshiro928**, but a cryptographically secure scrambler gives absolutely no detectable statistical weaknesses regardless of how the generated numbers are used. The speed of 'exro928ss' is only about 30-50% slower than the default fast 'rand' algorithm, but the state is roughly the double and it produces about 8 times the garbage per iteration. The speed of 'crypto_aes' is about half (amortized) that of the default fast 'rand' algorithm which is fast and thanks to doing encryption in batches caching the result. Hence the state is much larger.
2018-09-18Merge branch 'maint'Sverker Eriksson
2018-09-18Merge branch 'siri/cuddle' into maintSiri Hansen
* siri/cuddle: [logger] Skip app level test if app cannot be loaded Terminate nodes after failed test cases in erl_distribution_SUITE Skip performance test on build types other than 'opt'
2018-09-18Merge branch 'maint'Hans Bolinder
* maint: stdlib: Allow lists with binaries in the Format argument
2018-09-18Merge branch 'hasse/stdlib/binary_in_format/OTP-15304' into maintHans Bolinder
* hasse/stdlib/binary_in_format/OTP-15304: stdlib: Allow lists with binaries in the Format argument
2018-09-18Merge branch 'maint'Sverker Eriksson
2018-09-17test ets doc updatesverker-ets-patch-1Sverker Eriksson
2018-09-17stdlib: Allow lists with binaries in the Format argumentHans Bolinder
As a consequence of some refactoring (OTP-14983, option 'chars_limit'), the Format argument of io_lib:format() no longer accepts binaries in lists in Erlang/OTP 21.0. Note that if Format is not of type io:format(), control sequences in Format are ignored. This can result in unpredictable behaviour if, for example, the output of io_lib:format() is used as Format: if the output happens to be a string(), then control sequences are interpreted, otherwise not. A check that Format is of type io:format() will likely be introduced in Erlang/OTP 22.0. That will probably mean work for some users, but considering how unpredictable io_lib:format() is, we should try to fix that.
2018-09-17Merge branch 'maint'Siri Hansen
2018-09-17Skip performance test on build types other than 'opt'Siri Hansen
2018-09-13stdlib: Update ets docs for write_concurrency and ordered_setSverker Eriksson
2018-09-13Use long period counter for crypto_aesRaimo Niskanen
Conflicts: lib/crypto/doc/src/crypto.xml lib/crypto/src/crypto.erl
2018-09-13Prototype crypto_aes PRNGRaimo Niskanen
Conflicts: lib/crypto/src/crypto.erl
2018-09-13Improve seeding methodsRaimo Niskanen
2018-09-13Implement Xoroshiro928**Raimo Niskanen
2018-09-13Improve handling of ref valsRaimo Niskanen
2018-09-12[proc_lib] Improve crash reports for single line loggingSiri Hansen
2018-09-12[logger] Remove encoding option from logger_formatterSiri Hansen
The encoding option was introduced in commit 270d909696a753af022df72a404c73f2895b4a02, to allow report callbacks to format according to a given encoding. There was, however, no connection between this encoding option, and the encoding of the device to which the logger handler was writing. Since a formatter is defined to return unicode:chardata(), and in order to avoid mismatch with the encoding of the device, the encoding option is now removed from the formatter. The handler itself must make sure that it does not write illegal data to its device.
2018-09-10Clean up and optimize code and docRaimo Niskanen
2018-09-10Merge branch 'maint'Siri Hansen
2018-09-10Merge branch 'siri/supervisor/warn-shutdown-race/ERL-724' into maintSiri Hansen
* siri/supervisor/warn-shutdown-race/ERL-724: [supervisor] Add warning about race condition
2018-09-07[supervisor] Add warning about race conditionSiri Hansen
ERL-724: "During a 'gentle' shutdown, supervisors unlink from their children before sending shutdown signals to them. This can lead to a race condition in supervision trees, when the timeout for gentle shutdown of a parent supervisor expires and it kills a child supervisor that has just unlinked from a child of its own, leaving the child supervisor's own child still running after its supervisor is killed." This commit adds a warning about this in the documentation.
2018-09-06Merge branch 'maint'Rickard Green
* maint: Update PCRE from version 8.41 to version 8.42
2018-09-06Merge branch 'rickard/pcre-8.42/OTP-15217' into maintRickard Green
* rickard/pcre-8.42/OTP-15217: Update PCRE from version 8.41 to version 8.42
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-05Merge branch 'sverker/erts/ets-memstat-false-leak/ERL-720/OTP-15278' into maintSverker Eriksson
* sverker/erts/ets-memstat-false-leak/ERL-720/OTP-15278: erts: Refactor ets FixedDeletion allocations erts: Fix ets memstat false leak of FixedDeletion
2018-09-04Merge 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-08-31Fix type spec of ms_transform:parse_trans/2Péter Gömöri
It can also return errors and warnings.
2018-08-28Merge branch 'maint'Péter Dimitrov
* maint: Updated OTP version Update release notes stdlib: Let dets:open_file() crash when given raw file name Fix kernel_app doc logger_level default from info to notice Change-Id: I581946ac5cec6574ed79017e2987039c1fdcf80a
2018-08-28Merge pull request #1940 from ↵Hans Bolinder
uabboli/hb/stdlib/fix_dets_file_name/OTP-15253/ERL-555 stdlib: Let dets:open_file() crash when given raw file name
2018-08-27Merge branch 'maint'Hans Bolinder
* maint: Document allowed integer ops in types stdlib: Fix specs of filename:basedir/2,2
2018-08-22stdlib: Fix specs of filename:basedir/2,2Hans Bolinder
See also https://bugs.erlang.org/browse/ERL-667.
2018-08-21Merge branch 'maint'Hans Bolinder
* maint: stdlib: Correct contracts in module io_lib_format stdlib: Improve error handling in module io_lib
2018-08-21stdlib: Let dets:open_file() crash when given raw file nameHans Bolinder
See also ERL-55 and OTP-13229.
2018-08-20stdlib: Correct contracts in module io_lib_formatHans Bolinder
2018-08-20stdlib: Improve error handling in module io_libHans Bolinder
2018-08-16Merge branch 'josevalim/jv-sb/PR-1803/OTP-15238' into masterLukas Larsson
Optimize binary match from 10% up to 70x
2018-08-13Merge branch 'maint'Björn Gustavsson
* maint: Correct error behavior of is_map_key/2 in guards
2018-08-13Correct error behavior of is_map_key/2 in guardsBjörn Gustavsson
Consider the following functions: foo() -> bar(not_a_map). bar(M) when not is_map_key(a, M) -> ok; bar(_) -> error. What will `foo/0` return? It depends. If the module is compiled with the default compiler options, the return value will be `ok`. If the module is compiled with the `inline` option, the return value will be `error`. The correct value is `error`, because the call to `is_map_key/2` when the second argument is not a map should fail the entire guard. That is the way other failing guards BIFs are handled. For example: foo() -> bar(not_a_tuple). bar(T) when not element(1, T) -> ok; bar(_) -> error. `foo/0` always returns `error` (whether the code is inlined or not). This bug can be fixed by changing the classification of `is_map_key/2` in the `erl_internal` module. It is now classified as a type test, which is incorrect because type tests should not fail. Reclassifying it as a plain guard BIF corrects the bug. This correction also fixes the internal consistency check failure which was reported in: https://bugs.erlang.org/browse/ERL-699
2018-08-08Update PCRE from version 8.41 to version 8.42Rickard Green
2018-08-07Optimize binary matchJosé Valim
The idea is to use memchr on the first lookup for binary:match/2 and also after every match on binary:matches/2. We only use memchr in case of matches because benchmarks showed that using memchr even when we had false positives could negatively affect performance. This speeds up binary matching and binary splitting by 4x in some cases and by 70x in other scenarios (when the last character in the needle does not occur in the subject). The reason to use memchr is that it is highly specialized in most modern operating systems, often defaulting to SIMD operations. The implementation uses the reduction count to figure out how many bytes should be read with memchr. We could increase those numbers but they do not seem to make a large difference.