[erlang-questions] Changing the representation of sets

Michael Truog mjtruog@REDACTED
Tue Apr 25 09:18:38 CEST 2017

On 04/24/2017 11:51 PM, Michał Muskała wrote:
> Hello everybody.
> The sets module implements an opaque structure to represent sets. The current implementation is based on hashes and nested tuples. Since OTP 18, we have maps that are an excellent and performant data structure for storing arbitrary keys & values. This means, they can be used to efficiently implement sets, by storing set elements as keys with some default value.
> My measurements [1] show that a set implementation based on maps is 2-4 times faster in all operations than the current implementation from the sets module. Comparing performance tradeoffs to other set implementations, it seems that map-based sets have exactly the same characteristics as current sets, except they are faster. Map-based sets also have a huge advantage of being easily readable when printed in the console. Given the sets data structure is opaque it should be possible to just switch implementations and make everybody's code faster without changing a line of code. The only issue might be incorrect uses of the sets module that assume some particular shape for the structure - I'm not sure how widespread that is.
> Another possibility would be to implement a new map_sets module, but I think 4 set implementation is already too many - no need to add another. There's also no need to write a new implementation since there's already a well tested, map-based set implementation available in OTP in the cerl_sets module in the compiler application [2].
> A similar consideration could be made for the dict module, but I haven't looked closely at the performance differences there - I would expect something similar, though, since sets and dict use a similar implementation.
> Regards,
> Michał.
> [1]: https://gist.github.com/michalmuskala/9b0b55eee25b94d9339edbf7a0e261ea
> [2]: https://github.com/erlang/otp/blob/master/lib/compiler/src/cerl_sets.erl
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

It is best to avoid modifying dict and sets, due to unintended consequences.  One I can think of is the impact on memory allocation when a dict or sets is sent through distributed Erlang, since the memory allocation for a map larger than 32 elements (|MAP_SMALL_MAP_LIMIT|) gets an allocation from |HASHMAP_ESTIMATED_HEAP_SIZE(SIZE) == ||(SIZE*3 + (2*SIZE/5)*2) which can severely |exaggerate the size of the map (details in|erts/emulator/beam/erl_map.h|). There may be other impacts also, but that is unclear.  Keeping maps and dict/sets separate should be safest to avoid unintended changes in legacy source code.

Best Regards,

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20170425/62cb88ef/attachment.htm>

More information about the erlang-questions mailing list