Re: Lock-free LRU-cache-algorithm

From	Bonita Montero <Bonita.Montero@gmail.com>
Newsgroups	comp.lang.c++
Subject	Re: Lock-free LRU-cache-algorithm
Date	2019-08-13 10:24 +0200
Organization	albasani.net
Message-ID	<qits46$3pp$1@news.albasani.net> (permalink)
References	<qij5kb$fu3$1@news.albasani.net> <qissk1$1js7$2@gioia.aioe.org>

Show all headers | View raw

> There are lock-free doubly-linked lists. However, the following 
> algorihtm might of of interest to you:
> https://groups.google.com/d/topic/comp.lang.c++/sV4WC_cBb9Q/discussion
> It is a simple deadlock free hashed mutex algorihtm.

Your code might help exchaning two elements in a lock-free list with
a low likehood of a collision. But the thing I need is a LRU-list which
scales similar. The difference here is that an element is always pushed
to the top when it is touched. So every thread contending on that must
also lock the head-pointers. So if there is always a common´structure
locked, I can stick with a single lock and I would get the same effi-
ciency as your code.

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