[llvm-dev] High Performance containers

[Hal Finkel via llvm-dev]

On 08/17/2017 07:34 AM, Francois Fayard via llvm-dev wrote:
>
>> 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.

Speaking of benchmarks, we might be able use the library, or some parts 
of it, in our test suite for correctness and performance testing. I see 
some stand-alone benchmarks that seem useful (e.g., 
https://github.com/insideloop/InsideLoop/blob/master/il/benchmark/types/32-vs-64-bit-integers.cpp) 
but also some of the numeric things (e.g. 
https://github.com/insideloop/InsideLoop/blob/master/il/benchmark/memory/matrix_multiplication.cpp 
which makes use of SIMD pragmas and vector intrinsics). Something with 
the hash tables and multi-dimensional arrays could be useful too.

If you're interested (or anyone else is), I'm happy to chat more about 
the details.

  -Hal

>
> François Fayard
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/1a19c9cb/attachment.html>