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-09-24 13:58 -0700
Organization	Aioe.org NNTP Server
Message-ID	<qme01e$83n$2@gioia.aioe.org> (permalink)
References	<qij5kb$fu3$1@news.albasani.net> <qmdggf$4u4$1@news.albasani.net> <8SriF.3$1o3.1@fx09.iad> <qmdi3n$gc$1@news.albasani.net>

Show all headers | View raw

On 9/24/2019 10:00 AM, Bonita Montero wrote:
>> Hm. That's news, indeed.  Have you produced a formal proof?
> 
> There's nothing to prof. The idea isn't very complex,
> but it is very original.

It seems like you realized how bad CMPXCHG can be when used in a loop. 
Always try XADD and/or XCHG in a loopless algorihtm, before going to a 
CAS loop.


> 
>> You may want to consider LRU cache replacement algorithms
>> used in processor caches.
> 
> That's a totally different issue as the caches are basically
> pipelined, but within the pipeline each step is serialized.

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