5 ms·

Show HN: A header only C++11 LRU Cache template class, with no dependencies

29 points by mohaps 10y ago

tobz 10y ago
Can someone explain how this is headers-only? C/C++ are not my forte, but my limited interpretation of a "headers only" thing would be more along the lines of: it's only type definitions and preprocessor macros. It looks like there's plenty of actual method implementations being filled out there, but they just happen to be in a .hpp file instead of a .cpp file.
- mohaps 10y ago
  header-only usually means there's one or more .h/.hpp files that you can include in your source. There's no source file or library to compile and include e.g. if I had Hello.h and Hello.cpp, you'd need to either add Hello.cpp to your make/build or build a library and link to it. Header-only version means all you do is #include "Hello.h" and you're all set to go.
  - tobz 10y ago
    So in this case, headers-only is really just an approach to avoid compiling a separate library? More akin to literally including the source code in your source code, in the eyes on the compiler. All in the same object/library.
    - mohaps 10y ago
      mostly: yes! :) Also, keep in mind that most of the library is templates, which need to go in the header files. BTW, most of boost is header-only :) e.g. boost/noncopyable.hpp would give you a header only equivalent of the NoCopy class I wrote. I've always felt weird about having to include some big-arse library for just using a simple container, so for things like this I prefer to write header-only versions.
      - tobz 10y ago
        Cool. Thanks for the edification.
- deleted 10y ago
  [deleted]
- socmag 10y ago
  It means all the code is defined in-line in the header file, inside the class definition, instead of the more traditional method of using a header and an associated cpp file. A lot of the C++ standard library (STL) and Boost are header only (but not all) This means to use the code, all you need to do is #include the header file wherever you need it, rather than including a header file and either building a separate static/shared library for the cpp file, or including it in your own build. So that's really convenient. Another thing that happens is that the by doing this, the compiler can potentially do a lot better job of optimizing the code by inlining parts of the library straight into your calling function. With static libraries it is possible to get some optimizations like this made at link time, since link time code generation is a requirement for templates, but that's not possible with shared libraries since you are forced to call through an exported function entry point by their very nature. Header only libraries are typical for containers or light weight libraries where the cost of inclusion and possible code duplication of code is worth the performance gains, and certainly very popular where templates are involved. tl;dr, header only is cool just because they are so easy to consume and don't need a make file. Just #include and you are done.
  - tobz 10y ago
    Gotcha. Thanks for the detailed explanation.
aldanor 10y ago
Benchmarks / comparison to using other container types would be nice to have
- mohaps 10y ago
  yup! that's next up. :)
en4bz 10y ago
Not really sure why they reimplemented std::list. Also that NoCopy base class adds a vptr for no reason. And so do all those other virtual destructors. I personally wouldn't trust this code at first glance.
- mohaps 10y ago
  the kv::List is not intended as a generic linked list implementation like std::list. The reason for the specific implementation is to get constant time removal and remove-add_to_end operations. Truth be told, it is a hold-over from the previous implementation. I shall be writing benchmarks for this next up and shall revisit the decision on whether or not to use std::list soon-ish :) The : private NoCopy is just to block the copy constructors.
  - en4bz 10y ago
    You could have used std::list iterators instead of raw pointers to a node in the map to implement that.
    - mohaps 10y ago
      yeah, saw the gist posted by quinnftw. that actually is a better way to do what I'm doing. Will update that along with the cache.remove(const Key& k, F deleteCallback) method. Thanks for the feedback
    - mohaps 10y ago
      now i remember why I went with the old linked list implementation. with the std::list, everytime I refreshed a node... i did a copy. basically to the tune of list.push_back(*iter) where as I wanted to keep it as a simple unlink and relink of the node copy of the comment: https://news.ycombinator.com/item?id=12391069 https://news.ycombinator.com/item?id=12391069
      - en4bz 10y ago
        To swap nodes in the list you need to use splice like this: keys_.splice(keys_.begin(), keys_, iter->second); Where iter is from the cache lookup.
deleted 10y ago
[deleted]
speps 10y ago
So it's C++11 but still uses naked pointers...
- mohaps 10y ago
  the naked pointers are inside an internal kv namespace and are a convenience/carry over from the previous implementation (I've covered the justification for the way it's written in a comment above). the TL;DR is that it is written the way it is to achieve constant time remove/remove_and_add_to_end operations which is not an erase+append but more like an unlink/relink operation.
quinnftw 10y ago
Or if you want a non-obfuscated version https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04b9f https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04...
- mohaps 10y ago
  ah, now I remember why I had carried on with the linked list from the old c++ codebase https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04b9f#file-lru_cache-h-L28 https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04... the key refresh in std::list required a copy of the std::pair, where as I wished to keep it as an unlink / relink
- en4bz 10y ago
  Use splice to move items to the front of the list without copying in the find method.
WesternStar 10y ago
Looks like your insert function is missing an else . You're creating a new node when each time you find an existing node in the map.
- mohaps 10y ago
  thanks. fixed
cjhanks 10y ago
One of two (or both) things would need to be changed for it to be generally useful: - The return value should be a WeakPtr, not a bool and a reference. This allows for data to not be duplicated by all of the different `getter` threads. A WeakPtr<Type> is kind of C++'s equivalent of a Maybe<Type>. - The getter function also need to be passed a functor capable of generating the object, which then creates a `named lock` that /only/ other threads requesting that key. This duplicates multiple logical copies of the same item from being created (this is important when the creation is expensive, presumably the core reason for using an LRU cache). edit: formatting, I am not familiar with HN syntax.
psranga 10y ago
This line bothered me more than it should :) typedef std::string String; when using std::string; would have done just as well. Yes, I noticed the capitalization change. But why do you want to change the name of a fundamental type?

29 points by mohaps 10y ago

tobz 10y ago

Can someone explain how this is headers-only? C/C++ are not my forte, but my limited interpretation of a "headers only" thing would be more along the lines of: it's only type definitions and preprocessor macros. It looks like there's plenty of actual method implementations being filled out there, but they just happen to be in a .hpp file instead of a .cpp file.

mohaps 10y ago
header-only usually means there's one or more .h/.hpp files that you can include in your source. There's no source file or library to compile and include e.g. if I had Hello.h and Hello.cpp, you'd need to either add Hello.cpp to your make/build or build a library and link to it. Header-only version means all you do is #include "Hello.h" and you're all set to go.
- tobz 10y ago
  So in this case, headers-only is really just an approach to avoid compiling a separate library? More akin to literally including the source code in your source code, in the eyes on the compiler. All in the same object/library.
  - mohaps 10y ago
    mostly: yes! :) Also, keep in mind that most of the library is templates, which need to go in the header files. BTW, most of boost is header-only :) e.g. boost/noncopyable.hpp would give you a header only equivalent of the NoCopy class I wrote. I've always felt weird about having to include some big-arse library for just using a simple container, so for things like this I prefer to write header-only versions.
    - tobz 10y ago
      Cool. Thanks for the edification.
deleted 10y ago
[deleted]
socmag 10y ago
It means all the code is defined in-line in the header file, inside the class definition, instead of the more traditional method of using a header and an associated cpp file. A lot of the C++ standard library (STL) and Boost are header only (but not all) This means to use the code, all you need to do is #include the header file wherever you need it, rather than including a header file and either building a separate static/shared library for the cpp file, or including it in your own build. So that's really convenient. Another thing that happens is that the by doing this, the compiler can potentially do a lot better job of optimizing the code by inlining parts of the library straight into your calling function. With static libraries it is possible to get some optimizations like this made at link time, since link time code generation is a requirement for templates, but that's not possible with shared libraries since you are forced to call through an exported function entry point by their very nature. Header only libraries are typical for containers or light weight libraries where the cost of inclusion and possible code duplication of code is worth the performance gains, and certainly very popular where templates are involved. tl;dr, header only is cool just because they are so easy to consume and don't need a make file. Just #include and you are done.
- tobz 10y ago
  Gotcha. Thanks for the detailed explanation.

aldanor 10y ago

Benchmarks / comparison to using other container types would be nice to have

mohaps 10y ago
yup! that's next up. :)

en4bz 10y ago

Not really sure why they reimplemented std::list. Also that NoCopy base class adds a vptr for no reason. And so do all those other virtual destructors. I personally wouldn't trust this code at first glance.

mohaps 10y ago
the kv::List is not intended as a generic linked list implementation like std::list. The reason for the specific implementation is to get constant time removal and remove-add_to_end operations. Truth be told, it is a hold-over from the previous implementation. I shall be writing benchmarks for this next up and shall revisit the decision on whether or not to use std::list soon-ish :) The : private NoCopy is just to block the copy constructors.
- en4bz 10y ago
  You could have used std::list iterators instead of raw pointers to a node in the map to implement that.
  - mohaps 10y ago
    yeah, saw the gist posted by quinnftw. that actually is a better way to do what I'm doing. Will update that along with the cache.remove(const Key& k, F deleteCallback) method. Thanks for the feedback
  - mohaps 10y ago
    now i remember why I went with the old linked list implementation. with the std::list, everytime I refreshed a node... i did a copy. basically to the tune of list.push_back(*iter) where as I wanted to keep it as a simple unlink and relink of the node copy of the comment: https://news.ycombinator.com/item?id=12391069 https://news.ycombinator.com/item?id=12391069
    - en4bz 10y ago
      To swap nodes in the list you need to use splice like this: keys_.splice(keys_.begin(), keys_, iter->second); Where iter is from the cache lookup.

deleted 10y ago

[deleted]

speps 10y ago

So it's C++11 but still uses naked pointers...

mohaps 10y ago
the naked pointers are inside an internal kv namespace and are a convenience/carry over from the previous implementation (I've covered the justification for the way it's written in a comment above). the TL;DR is that it is written the way it is to achieve constant time remove/remove_and_add_to_end operations which is not an erase+append but more like an unlink/relink operation.

quinnftw 10y ago

Or if you want a non-obfuscated version https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04b9f https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04...

mohaps 10y ago
ah, now I remember why I had carried on with the linked list from the old c++ codebase https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04b9f#file-lru_cache-h-L28 https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04... the key refresh in std::list required a copy of the std::pair, where as I wished to keep it as an unlink / relink
en4bz 10y ago
Use splice to move items to the front of the list without copying in the find method.

WesternStar 10y ago

Looks like your insert function is missing an else . You're creating a new node when each time you find an existing node in the map.

mohaps 10y ago
thanks. fixed

cjhanks 10y ago

One of two (or both) things would need to be changed for it to be generally useful: - The return value should be a WeakPtr, not a bool and a reference. This allows for data to not be duplicated by all of the different `getter` threads. A WeakPtr<Type> is kind of C++'s equivalent of a Maybe<Type>. - The getter function also need to be passed a functor capable of generating the object, which then creates a `named lock` that /only/ other threads requesting that key. This duplicates multiple logical copies of the same item from being created (this is important when the creation is expensive, presumably the core reason for using an LRU cache). edit: formatting, I am not familiar with HN syntax.

psranga 10y ago

This line bothered me more than it should :) typedef std::string String; when using std::string; would have done just as well. Yes, I noticed the capitalization change. But why do you want to change the name of a fundamental type?