8000 Route Set / UnorderedSet operations to the BEAM's native set BIFs · Issue #209 · kexhq/kex · GitHub
[go: up one dir, main page]

Skip to content

Route Set / UnorderedSet operations to the BEAM's native set BIFs #209

Open

Description

@akoskovacs

Follow-up to #98, which landed Set and UnorderedSet as pure Kex.

The representations were chosen to match OTP's own, so this is an
implementation swap with no change to what a set IS:

  • Set is {'Set', SortedList} — the ordsets representation exactly.
  • UnorderedSet is {'UnorderedSet', Map} — the sets v2 representation
    exactly (sets:new([{version, 2}]) is a map).

So ordsets:union/2, ordsets:intersection/2, ordsets:subtract/2,
maps:with/2, maps:without/2 and friends can be called on the field
directly. Today those operations are Kex loops over the elements; on BEAM they
could each be one BIF.

What makes this more than a -D in the emitter: intrinsics have to work on
BOTH backends, so each one needs a C++ implementation for the tree walker
beside the BEAM route. That is the same shape as the existing
Kex.Intrinsic.Map.* and Kex.Intrinsic.List.* families.

Not in scope: adopting gb_sets. It is an opaque term the tree walker cannot
produce, so it would make Set a type only one backend can build.

Worth measuring before doing: Set.contains? is a linear scan of a sorted
list and is the most likely thing to actually hurt, while union on
UnorderedSet already lowers to maps:merge.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    EnhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      0