[llvm-dev] High Performance containers

[Francois Fayard via llvm-dev]

> You can imagine a community the size of LLVM's having to rely on
> external libraries that may have the same goals today, but different
> paths tomorrow. The end result is the same: a fork for the things that
> matter to us, just like we've done with the standard library.
> 
> All in all, your library looks really nice, and it does solve an
> intersection of the problems we also solve, probably in very similar
> ways, but that doesn't mean source code can be shared at that level.
> There are other factors at play which have nothing to do with solving
> problems.

I agree with you. And I never thought that sharing the same source code could be something that can be done.

But sharing ideas, implementation tricks, algorithms (I am thinking about all the probing methods available in open addressing) might be helpful. That’s were we can share ideas. Scientific computing is more and more about computing on strings (think DNA), and data structures such as graphs which are not as simple as the good old days where BLAS workloads where the only ones.

To be honest, I’d like to get the best of ADT and understand the rationale behind some choices. In return, I might bring you some time to test new ideas and I can try to give ideas that could also be implemented in LLVM. For me, what is time consuming is not coding, but designing APIs that are both easy to use, difficult to misuse, and don’t lock performance. Getting the 3 of them right (or as close as you can) is really hard work.
Just to give, you an idea, here is how my hash map works if you want to do memoization
=====
B f(A x);

il::Map<A, B> map{};

B f_memoization(A x) {
  // If x is in the map, i is the slot where the key, value pair is
  // It it is not the case, it is the place where it should be inserted
  // All in all, this algo, hashes x and runs the hash table only one
  const int i = map.search(x);
  if (!map.found(x)) {
    map.insert(x, f(x), i);
  }
  return map.value(i);
}
=====
Doing the same with the STL is just painful. This example by the way comes from one of Chandler Carruth’s talk.

What I am looking for is sharing ideas, running some benchmarks, working on pros and cons of APIs on a performance point of view, etc. It anyone think that this could be helpful, it would be great.

François Fayard
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/717aa955/attachment.html>