3 ms·

Something you may find interesting is that the new faster maps are loosely based on Rich Hickey's HAMT implementation that is used in Clojure. Jose and co. in E

by jlouis 11y ago

Something you may find interesting is that the new faster maps are loosely based on Rich Hickey's HAMT implementation that is used in Clojure. Jose and co. in Elixir adapted/is-adapting their internals to use maps as well, as they were faster than any implementation they had. In addition, I wrote a full QuickCheck model for the new maps. That is, we randomly generate unit test cases for the maps and verify them. We have generated several millions of those test cases, including variants which heavily collides on the hash. This weeded out at least 10 grave bugs from the implementation, which in turn means this release is probably very stable with respect to maps.

passwordis 11y ago
Isn't HAMT Phil Bagwell ?
istvan__ 11y ago
No surprise there, Rich's code is pretty solid. I really like this sort of co-operation between languages. Out of curiosity: QuickCheck is a property based test library? I know of test.check in Clojure and they mention QuickCheck as the inspiration, so I guess they re similar in this regard.
- masklinn 11y ago
  Yes. QuickCheck the original property-based test library, initially for Haskell then commercially ported by the original author to Erlang (as Quviq QuickCheck) http://www.cse.chalmers.se/~rjmh/QuickCheck/ http://www.cse.chalmers.se/~rjmh/QuickCheck/ http://www.quviq.com/products/erlang-quickcheck/ http://www.quviq.com/products/erlang-quickcheck/
- jlouis 11y ago
  The base is the same, but Quviq QuickCheck for Erlang provides some libraries which are far more developed than most QuickCheck implementations out there. On the other hand, it is not a free tool if you want the full version. Since you are searching randomly, you need good heuristics that skews the distribution toward where "errors often occurs". This means errors are uncovered in fewer test cases. Also, you need good heuristics for minimizing/shrinking a known failing error. Some of the error cases shrank from 80 commands down to 5, and furthermore simplified the input so it was easier to see what stood out.
polack 11y ago
Are the quickcheck tests in the otp repo? Cannot find them, but I guess it makes some sense to leave them out since not all have the full quickcheck installed.
- jlouis 11y ago
  It currently lives in its own repository: https://github.com/jlouis/maps_eqc https://github.com/jlouis/maps_eqc There is also an accompanying series of blog posts: https://medium.com/@jlouis666/breaking-erlang-maps-4-4ebc3c64068c https://medium.com/@jlouis666/breaking-erlang-maps-4-4ebc3c6... (Part 4 here links to the other 3 parts in the beginning for interested readers).
pselbert 11y ago
Some great articles about the process of "Breaking Erlang Maps" via QuickCheck. Thanks for those! 1: https://medium.com/@jlouis666/breaking-erlang-maps-1-31952b8729e6 https://medium.com/@jlouis666/breaking-erlang-maps-1-31952b8... 2: https://medium.com/@jlouis666/breaking-erlang-maps-2-362730a91400 https://medium.com/@jlouis666/breaking-erlang-maps-2-362730a...

by jlouis 11y ago

passwordis 11y ago

Isn't HAMT Phil Bagwell ?

istvan__ 11y ago

No surprise there, Rich's code is pretty solid. I really like this sort of co-operation between languages. Out of curiosity: QuickCheck is a property based test library? I know of test.check in Clojure and they mention QuickCheck as the inspiration, so I guess they re similar in this regard.

masklinn 11y ago
Yes. QuickCheck the original property-based test library, initially for Haskell then commercially ported by the original author to Erlang (as Quviq QuickCheck) http://www.cse.chalmers.se/~rjmh/QuickCheck/ http://www.cse.chalmers.se/~rjmh/QuickCheck/ http://www.quviq.com/products/erlang-quickcheck/ http://www.quviq.com/products/erlang-quickcheck/
jlouis 11y ago
The base is the same, but Quviq QuickCheck for Erlang provides some libraries which are far more developed than most QuickCheck implementations out there. On the other hand, it is not a free tool if you want the full version. Since you are searching randomly, you need good heuristics that skews the distribution toward where "errors often occurs". This means errors are uncovered in fewer test cases. Also, you need good heuristics for minimizing/shrinking a known failing error. Some of the error cases shrank from 80 commands down to 5, and furthermore simplified the input so it was easier to see what stood out.

polack 11y ago

Are the quickcheck tests in the otp repo? Cannot find them, but I guess it makes some sense to leave them out since not all have the full quickcheck installed.

jlouis 11y ago
It currently lives in its own repository: https://github.com/jlouis/maps_eqc https://github.com/jlouis/maps_eqc There is also an accompanying series of blog posts: https://medium.com/@jlouis666/breaking-erlang-maps-4-4ebc3c64068c https://medium.com/@jlouis666/breaking-erlang-maps-4-4ebc3c6... (Part 4 here links to the other 3 parts in the beginning for interested readers).

pselbert 11y ago

Some great articles about the process of "Breaking Erlang Maps" via QuickCheck. Thanks for those! 1: https://medium.com/@jlouis666/breaking-erlang-maps-1-31952b8729e6 https://medium.com/@jlouis666/breaking-erlang-maps-1-31952b8... 2: https://medium.com/@jlouis666/breaking-erlang-maps-2-362730a91400 https://medium.com/@jlouis666/breaking-erlang-maps-2-362730a...