6 ms·
C++: Associative map containers with compile-time lookup
- petters 8y agoI can see how `semi::map` could be useful, but `semi::static_map` just seems to be an alternate syntax for global variables.
- nightfly 8y agoBut somehow slower! "In fact, when using semi::static_map and looking up a value with C++ literal as a key, then the value lookup is nearly as efficient as looking up a global variable."
- hogliux 8y agoYes with the optional run-time lookup there is an extra two machine instructions (a cmp and jne) needed to check if this is the first time accessing the value. It is exactly as fast as a global variable if you don't need the optional run-time lookup. As stated in the talk, the main use case for a map like this is to cache objects which are expensive to load/compute (again something like `getFont` comes to mind). In these use-cases you would likely also need a check like this anyway: a global pointer object which you need to check if it's a nullptr or not before using it.
- quotemstr 8y agoNot exactly as fast. Without -Bsymbolic, a global variabile with global symbol visibility gets its own GOT entry, meaning access to your global goes through an indirection table that supports ELF symbol interposition. (Which, IMHO, was a bad idea, but you can't unbreak an egg.) With a data structure like this (or with a conventional "struct globals"), there's one symbol at the ELF level to look up instead of one per variable, so your code might end up doing fewer GOT lookups. The last paragraph was just arcana though. You should be passing -fvisibility=hidden and explicitly exporting from your DSO only the symbols you might legitimately expect some other DSO to use, obviating the issue.
- hogliux 8y agoThanks, I'll have a look at this!
- jstimpfle 8y agoLook at the approach from my other comment. Requires only 1 symbol.
- hogliux 8y agoBoth your approach and the `semi::static_map` will generate the same type of load instruction. In both cases, the compiler knows the offset of the values in memory at compile-time. The number of symbols is not really important here.
- hogliux 8y agoYes, in a way you are right: the compiler really does boil it down to global variables. However, `semi::static_map` gives you some additional features, which may be useful for a lot of situations 1) `semi::static_map` gives you the optional run-time look-up with the same API (`semi::static_map::get`). Looking up a global variable with a runtime key isn't straight-forward. This makes it particularly nice to use an API where a function might take either a compile-time or run-time key. I'm thinking a Font API with a `getFont` method, for example. The way you use the method is the same regardless if you are using a compile-time key or not. 2) `semi::static_map` also gives you control over the lifetime of the objects. For example, it's easy to delete all the values in the map at once. Again, this is not straight-forward to do with a bunch of globals. 3) the keys are also values themselves and it's straight-forward to evaluate them at run-time. Printing the name of a global variable, for example, requires all sorts of hackery. 4) you do not need to know all your keys in advance. Simply using getFont with a unique constexpr key will create a new global variable. Edit: added point (4)
- petters 8y agoThanks for this clarification! I agree it can be useful.
- jstimpfle 8y agoRe: 3), here's a clean and technically humble way that I typically use. enum { KEY_FOO, KEY_BAR, KEY_BLAH, NUM_KEYS, }; struct KeyInfo { const char *name; int info1; float info2; }; const static struct KeyInfo keyInfo[NUM_KEYS] = { #define MAKE(x, y, z) [x] = { #x, y, z } MAKE( KEY_FOO, 1, 1.0 ), MAKE( KEY_BAR, 7, 3.5 ), MAKE( KEY_BLAH, 42, 127.2 ), #undef MAKE }; void print_key(int key) { printf("%d's name is %s\n", key, keyInfo[key].name); } It's both low-tech and maintainable. It compiles super quick. If one doesn't like that one has to type KEY_FOO twice (in the enum and in the array definition), one can use X-macros or code generation. But personally I don't care.
- hogliux 8y ago
- deleted 8y ago[deleted]
- Nalta 8y agoTrue, but I think this could really be useful for cases similar to google flags (https://github.com/gflags/gflags https://github.com/gflags/gflags) wherein each file in a library adds to the global configuration. Then your main can more easy parse out these options to be shared across the entire codebase.
- drej 8y agoCppCon has super interesting content. That comes from a person who has written maybe two dozen lines of C++ code, mostly just hello world. E.g. this talk by Matt Godbolt or anything by Chadler Carruth. https://www.youtube.com/watch?v=bSkpMdDe4g4 https://www.youtube.com/watch?v=bSkpMdDe4g4
- deleted 8y ago[deleted]
- quickben 8y agoAnything from Chandlery on C++ performance is worth gold.
- Nimelrian 8y agoAlso highly recommended: Anything by Jason Turner and Ben Deane. Examples: - Ben Deane - Using Types Effectively [0] - Jason Turner - Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17 [1] - Ben Deane & Jason Turner - constexpr ALL the Things! [2] [0] https://www.youtube.com/watch?v=ojZbFIQSdl8 https://www.youtube.com/watch?v=ojZbFIQSdl8 [1] https://www.youtube.com/watch?v=zBkNBP00wJE https://www.youtube.com/watch?v=zBkNBP00wJE [2] https://www.youtube.com/watch?v=PJwd4JLYJJY https://www.youtube.com/watch?v=PJwd4JLYJJY
- drej 8y agoThanks! And just today, compile time regular expressions https://www.youtube.com/watch?v=QM3W36COnE4 https://www.youtube.com/watch?v=QM3W36COnE4
- jcelerier 8y agoare there fundamental differences with https://github.com/serge-sans-paille/frozen https://github.com/serge-sans-paille/frozen ?
- nemoniac 8y agoC++ is getting more and more like Lisp.
- stochastic_monk 8y agoThe functional programming concepts which have made it into C++1[147] have made programming in C++ much easier, more concise, and quite fast. I think they’re among the better recent additions to the language. Lambdas, for_each, transform, and accumulate all see regular use in my code.
- carlmr 8y agoA secret cabal of Lisp programmers took over the C++ steering committee.
- de_watcher 8y agoIt has started long ago with STL.
- vaylian 8y agoSeems like Greenspun's tenth rule is in effect here.
- jstimpfle 8y agoNow even the linker gets reinvented as unreadable templates? Is there a benefit?
- cjaybo 8y agoThanks for sharing. I'm a big fan of your work on the JUCE framework!
- jordigh 8y agoThis is a sore point for me in D. Assoc arrays in D don't work at compile time. It's a really longstanding issue: https://issues.dlang.org/show_bug.cgi?id=1578 https://issues.dlang.org/show_bug.cgi?id=1578 It's a real shame because I prefer just about everything else about metaprogramming and compile-time evaluation in D over C++.
- atilaneves 8y agoYou can write your own in D though.
- jordigh 8y agoI don't know how to yet. And if this is possible, is it also possible to fix standard assoc arrays?
- atilaneves 8y ago> is it also possible to fix standard assoc arrays? AFAIK, yes, it's just that nobody has done that yet. The D runtime was written before there were templates, and it shows.
- sriram_sun 8y ago#define ID(x) []() constexpr { return x; } Interesting! Macro substitutions can expand to anything of course. I hadn't really considered adding lambda functions to that list.
- hogliux 8y agoI'm looking forward to C++-20 when this is not needed anymore :-) - it will support string literals as non-type template parameters.
- gumby 8y agoThis looks really cool. Why add a different type static_map instead of using a constexpr declaration?
- hogliux 8y agoBecause with a constexpr declaration everything will be constexpr, i.e. you couldn't modify the values at run-time. The idea here is that finding the storage of the value is done at compile-time, but the values themselves are run-time values.
- gumby 8y agoThanks, I wasn't very clear but now I see the problem. The C++ invocation syntax (basically the difference between expressions and statements inherited from Algol) makes it impossible to call if you want to update it at runtime. You could declare `static static_map<>::Value& get()` constexpr. (Actually you wouldn't need to; I think you could simply declare `semi::map<>::get()` to be constexpr) and I believe it would allow calling to look up a value to inlined at compile time. However using it as an lvalue isn't possible with current c++ syntax. As a long time Lisp programmer this limitation continually trips me up. Sorry about the backquotes; I know that HN doesn't use MD but it was the simplest way to denote code inline.
- hogliux 8y agoHmmm, I'm not sure I understand. You can't really mark `static static_map<>::Value& get()` constexpr because it returns a value which is only known at run-time - again the value is a run-time value, only the lookup (where in memory) is at compile-time. This has nothing to do with inlining.
- gumby 8y agoAhh, I looked in the source and see that runtime_map is simply a std::unordered_map. I didn't look closely enough and assumed you'd made your own hash lookup so that parts of it could be run at compile time (in fact you could intern compile-time keys statically in the front of an object (in the initialized data section of the object file) adding a single additional probe at runtime) and let the linker patch up the locations in the usual fashion. This is all a move in the right direction!
- singularity2001 8y agojust tried C++ after some time and was set back by: * no []= operator in custom maps * no enum printing * no backtrace * other random desasters At least they don't work without jumping through some hoops in all of your code. So for me c++ is about as fixable/appealing as Fortran. https://stackoverflow.com/questions/3342726/c-print-out-enum-value-as-text#3342891 https://stackoverflow.com/questions/3342726/c-print-out-enum... https://stackoverflow.com/questions/691719/c-display-stack-trace-on-exception https://stackoverflow.com/questions/691719/c-display-stack-t... https://stackoverflow.com/questions/3581981/overloading-the-c-indexing-subscript-operator-in-a-manner-that-allows-for-r#3582101 https://stackoverflow.com/questions/3581981/overloading-the-...