Re: Lock-free LRU-cache-algorithm

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups	comp.lang.c++
Subject	Re: Lock-free LRU-cache-algorithm
Date	2019-10-16 14:16 -0700
Organization	Aioe.org NNTP Server
Message-ID	<qo81c8$p7v$1@gioia.aioe.org> (permalink)
References	<qij5kb$fu3$1@news.albasani.net> <qmdggf$4u4$1@news.albasani.net> <qmdvic$6c6$1@gioia.aioe.org> <qo76la$ll7$1@news.albasani.net>

Show all headers | View raw

On 10/16/2019 6:40 AM, Bonita Montero wrote:
>> https://groups.google.com/d/msg/comp.arch/8Y0C8zGjtqI/bwg-hBLRAQAJ
> 
> A lock-free stack is the simplest kind of lock-free algorithm.

Humm... Actually mutating a counter with fetch-and-add is very simple. 
Vs locking and unlocking a mutex to perform the same mutation. The lock 
free LIFO is way more complex. Its not the simplest. Btw, do you take 
membars into account? Updating the counter can be a single liner and use 
relaxed memory order. Simple. Going for LIFO, well, you need to get the 
membars right wrt push and pop. Unless you are using some really exotic 
methods. Epoch periods and such.



> 
> My LRU-algorithm has the following properties: it has a hashtable as
> well as a LRU-list. The hashtable points to the nodes in the LRU-list.
> For a cache-hit in the hashtable, pushing the LRU-entry to the head of
> the LRU-list is kernel-contention-free in almost any case (how often
> is configurable). As cache-hits have a high freqeuency parallel updates
> are very essential. Inserts into the hashtable and the LRU-list as well
> as flushes from the LRU-list occur conventionally locked. But this does
> not really hurt because it happens by far not that often but only at
> times when blocks are fetched from  disk / ssd; and this has a lower
> frequency by nature.
> Here's a graph of the performance of my algorithm:
> https://abload.de/image.php?img=performancekkklx.png
> The groups arre the graphs according to the number of threads running.
> On the vertical axis you can see the number of updates which occured
> per second. Within the groups the bars have a growing parameter which
> controls how often kernel-contention is necessary. For the rightmost
> groups this hasn't pushed to a reasonable maximum as the performance
> hasn't logarithmically hit the top trougput. With this benchmark I'm
> randomly give inserts into the hashtable / LRU-list at an average of
> 150 iterations to have a realistic disk-slowdown.

Thread

Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-09 08:59 +0200
  Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-09 05:14 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-09 16:32 +0200
      Re: Lock-free LRU-cache-algorithm Melzzzzz <Melzzzzz@zzzzz.com> - 2019-08-09 14:38 +0000
  Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson " <ahh_f_it@crap.nothing> - 2019-08-10 02:09 -0700
    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-10 02:12 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 11:42 +0200
      Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-10 03:48 -0700
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 13:21 +0200
          Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-10 05:30 -0700
            Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 15:52 +0200
              Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-10 09:40 -0700
                Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-26 00:55 -0700
                Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-26 10:02 +0200
  Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-12 19:48 +0200
  Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-12 16:26 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 10:24 +0200
      Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 23:51 -0700
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 23:55 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 10:42 +0200
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 11:19 +0200
        Re: Lock-free LRU-cache-algorithm Josef Moellers <josef.moellers@invalid.invalid> - 2019-08-13 11:42 +0200
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 12:47 +0200
      Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 15:03 -0700
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 15:17 -0700
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 15:31 -0700
  Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-24 18:33 +0200
    Re: Lock-free LRU-cache-algorithm scott@slp53.sl.home (Scott Lurndal) - 2019-09-24 16:53 +0000
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-24 19:00 +0200
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-24 13:58 -0700
    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-24 13:50 -0700
      Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-24 13:56 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-16 15:40 +0200
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-16 16:25 +0200
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-16 14:16 -0700
    Re: Lock-free LRU-cache-algorithm Juha Nieminen <nospam@thanks.invalid> - 2019-09-25 06:42 +0000
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 09:08 +0200
        Re: Lock-free LRU-cache-algorithm Juha Nieminen <nospam@thanks.invalid> - 2019-09-25 10:12 +0000
          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 13:37 +0200
            Re: Lock-free LRU-cache-algorithm scott@slp53.sl.home (Scott Lurndal) - 2019-09-25 12:55 +0000
              Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 15:28 +0200
                Re: Lock-free LRU-cache-algorithm Juha Nieminen <nospam@thanks.invalid> - 2019-09-25 17:23 +0000
                Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 20:19 +0200
      Re: Lock-free LRU-cache-algorithm David Brown <david.brown@hesbynett.no> - 2019-09-25 10:10 +0200
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 22:59 -0700
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:09 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-08 13:33 +0200
      Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-10-08 08:31 -0700
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-08 17:45 +0200
  Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:11 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-26 08:13 +0200
      Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:33 -0700
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:34 -0700
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-26 11:13 +0200
          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-26 20:37 +0200
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-23 19:42 -0700
            Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-24 11:00 +0200
              Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-24 13:13 -0700
                Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-24 13:14 -0700
                Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-25 06:53 +0200
                Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-24 23:06 -0700
                Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-25 08:20 +0200
                Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-25 21:35 -0700
                Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-25 21:37 -0700
                Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-26 08:39 +0200
  Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:49 -0700
  Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-21 16:42 +0200

csiph-web