Hi Dean. Thanks for your reply. The ADT library is exactly what I end up replicating. My library started 2 years ago and at the beginning, what I needed was very different from LLVM. My first containers were: - A custom std::vector that does not initialize elements to 0 for int, double, etc. This is very important in HPC for the first touch policy used on NUMA architectures. It also allows alignement to vector width which can be important for performance with vectorization. - A small size optimized vector - Multidimensional arrays That’s later, when I discovered Chandler Carruth’s talks, that I discovered that I was not the only one having issues with the STL. My hash map, is almost the same as LLVM one. I also have a hash set, a view on a string, and a unicode friendly string which can handle UTF8 as an invariant and which is implemented the same way std::string is implemented in libc++. Where I might bring some help, is with the probing method in map and with the default hashing functions. There are some hashing strategies such as robin hood hashing that might be worth trying. Also I know, that the hashing strategy for integers in LLVM is suboptimal. But I am not sure it would give a lot of help as I don’t think LLVM hashes a lot on integers. François Fayard> On Aug 17, 2017, at 10:23 AM, Dean Michael Berris <dean.berris at gmail.com> wrote: > > Hi Francois, > > Have you looked at the ADT library in LLVM, and have you considered contributing to LLVM directly (and improving the available data structures / algorithms in the codebase)? > > I understand that might not meet the goal of something that is released and supported by the LLVM project (i.e. a standalone containers/adapters library) but I suspect something that developers working on LLVM passes and/or the compilers can use. > > Good luck with the project, BTW. :) > > Cheers-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/32df1584/attachment.html>
On 17 August 2017 at 12:39, Francois Fayard via llvm-dev <llvm-dev at lists.llvm.org> wrote:> The ADT library is exactly what I end up replicating.This is a very common occurrence. The problems are similar, the implementations slightly different and adaptation becomes really hard, so everyone develops their own. I don't think many people will consider replacing the ADT (et al) for some external library, no matter how good it is. Not based on the merits of your library, but on the usefulness of replacing a well known and fine tuned library with an unknown one that solves pretty much the same problems and can't really be that much faster. Plus, we have very little use for BLAS-like functionality, which is the bulk of most HPC libraries. 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. cheers, --renato
> 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>