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

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

#21

Post by _lbaq » Tue, Aug 30, 2016, 2:41 PM UTC

mohaps wrote: post #15

en4bz wrote: post #10

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.

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 bl…

>The : private NoCopy is just to block the copy constructors.

If its C++11 why not just use the delete keyword to prevent auto generating members ?

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

#22

Post by WesternStar » Tue, Aug 30, 2016, 2:42 PM UTC

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.

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

#23

Post by Someone » Tue, Aug 30, 2016, 2:47 PM UTC

mohaps wrote: post #15

en4bz wrote: post #10

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.

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 bl…

"The reason for the specific implementation is to get constant time removal and remove-add_to_end operations"

http://en.cppreference.com/w/cpp/container/list:

"std::list is a container that supports constant time insertion and removal of elements from anywhere in the container."

'The : private NoCopy is just to block the copy constructors."

But does it need a virtual destructor?

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

#24

Post by mohaps » Tue, Aug 30, 2016, 2:56 PM UTC

WesternStar wrote: post #22

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.

thanks. fixed

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

#25

Post by quinnftw » Tue, Aug 30, 2016, 2:59 PM UTC

mohaps wrote: post #15

en4bz wrote: post #10

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.

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 bl…

Personally I would use a macro such as:

    #define DISALLOW_COPY_AND_ASSIGN(TypeName) \
    TypeName(TypeName&) = delete;              \
    void operator=(TypeName) = delete;

Introducing a virtual base class for disabling copying introduces a vtable and un-needed inheritance.

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

#26

Post by mohaps » Tue, Aug 30, 2016, 3:35 PM UTC

quinnftw wrote: post #16

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

ah, now I remember why I had carried on with the linked list from the old c++ codebase

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

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

#27

Post by mohaps » Tue, Aug 30, 2016, 3:37 PM UTC

en4bz wrote: post #19

mohaps wrote: post #15

Earlier quoted context omitted.

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 bl…

You could have used std::list iterators instead of raw pointers to a node in the map to implement that.

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

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

#28

Post by en4bz » Tue, Aug 30, 2016, 3:45 PM UTC

mohaps wrote: post #27

en4bz wrote: post #19

Earlier quoted context omitted.

You could have used std::list iterators instead of raw pointers to a node in the map to implement that.

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

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.

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

#29

Post by en4bz » Tue, Aug 30, 2016, 3:53 PM UTC

quinnftw wrote: post #16

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

Use splice to move items to the front of the list without copying in the find method.

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

#30

Post by cjhanks » Tue, Aug 30, 2016, 5:19 PM UTC

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 is kind of C++'s equivalent of a Maybe.

- 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.