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-23 19:42 -0700
Organization	Aioe.org NNTP Server
Message-ID	<qor321$1mf4$1@gioia.aioe.org> (permalink)
References	<qij5kb$fu3$1@news.albasani.net> <qmhkqn$ih4$2@gioia.aioe.org> <qmhkv3$msk$1@news.albasani.net> <qmhm3c$och$1@gioia.aioe.org> <qmhvgi$sej$1@news.albasani.net>

Show all headers | View raw

On 9/26/2019 2:13 AM, Bonita Montero wrote:
>>>> can I sign an NDA?
> 
>>> Why?
> 
>> I am interested in your algorithm! Makes me think of times past.
> 
> Something different: my algorithm is fast when fetching blocks from
> the lru-cache present in the cache, i.e. there can be an arbitrary
> number of threads doing that. But even this needs at least three
> CMPXCHGs on three 64 bit values (in a 64-bit-system, in a 32-bit
> system you would have two 64- and one 32-bit exchange) if there's
> no collision.

Are you using an embedded version count within the data the CAS's work 
on? Like an ABA counter? If a CAS fails, how far back do you have to 
restart, or unroll if you will?




  I'm asking myself if this would be faster with trans-
> actional memory, i.e if I'd build something similar like CMPXCHG
> with TSX-RTM, if this would be faster.
> I could redesign my "cachline ping pong" code to use TSX-RTM with-
> out having tested this on my PC; so could anyone here run the num-
> bers on that?

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