• via Digitalmars-d-bugs (30/30) Apr 04 2016 https://issues.dlang.org/show_bug.cgi?id=15871

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=15871

          Issue ID: 15871
           Summary: Implement SIMD-friendly set intersection
           Product: D
           Version: D2
          Hardware: x86_64
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: dmitry.olsh gmail.com

See the paper:
http://www.vldb.org/pvldb/vol8/p293-inoue.pdf
And related SIMD galloping:
http://boytsov.info/pubs/simdcompressionarxiv.pdf

Quoting the first paper:

Our algorithm is suitable to 
replace existing standard library functions, such as
std::set_intersection in C++, thus accelerating many applications,
because the algorithm is simple and requires no preprocessing to
generate additional data structures. We implemented our
algorithm on Xeon and POWER7+. The experimental results
show our algorithm outperforms the std::set_intersection
implementation delivered with gcc by up to 5.2x using SIMD
instructions and by up to 2.1x even without using SIMD
instructions for 32-bit and 64-bit integer datasets.

Worth looking into.

--