Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #67469 > unrolled thread

Lock-free LRU-cache-algorithm

Back to article view | Back to comp.lang.c++

Contents

  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

Page 1 of 4  [1] 2 3 4  Next page →

#67469 — Lock-free LRU-cache-algorithm

Can anyone tell how a lock-free algorithm for a LRU-cache would
look like? LRU-caches are only possible with doubly-linked lists.
So I thought this woudn't be possible lock-free. But maybe I'm
wrong here and someone can give me an idea.

[toc] | [next] | [standalone]

#67476

On Friday, 9 August 2019 09:59:33 UTC+3, Bonita Montero  wrote:
> Can anyone tell how a lock-free algorithm for a LRU-cache would
> look like? LRU-caches are only possible with doubly-linked lists.
> So I thought this woudn't be possible lock-free. But maybe I'm
> wrong here and someone can give me an idea.

One way is to add a thread that manages the cache.

[toc] | [prev] | [next] | [standalone]

#67481

>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>> look like? LRU-caches are only possible with doubly-linked lists.
>> So I thought this woudn't be possible lock-free. But maybe I'm
>> wrong here and someone can give me an idea.

> One way is to add a thread that manages the cache.

And that's lock-free??? ;-)

[toc] | [prev] | [next] | [standalone]

#67484

On 2019-08-09, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>>> look like? LRU-caches are only possible with doubly-linked lists.
>>> So I thought this woudn't be possible lock-free. But maybe I'm
>>> wrong here and someone can give me an idea.
>
>> One way is to add a thread that manages the cache.
>
> And that's lock-free??? ;-)

Take a look at Linux kernel...
>


-- 
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi 
bili naoruzani. -- Mladen Gogala

[toc] | [prev] | [next] | [standalone]

#67517

On 8/8/2019 11:59 PM, Bonita Montero wrote:
> Can anyone tell how a lock-free algorithm for a LRU-cache would
> look like? LRU-caches are only possible with doubly-linked lists.
> So I thought this woudn't be possible lock-free. But maybe I'm
> wrong here and someone can give me an idea.

Perhaps a lock-free deque?

[toc] | [prev] | [next] | [standalone]

#67518

On 8/10/2019 2:09 AM, Chris M. Thomasson  wrote:
> On 8/8/2019 11:59 PM, Bonita Montero wrote:
>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>> look like? LRU-caches are only possible with doubly-linked lists.
>> So I thought this woudn't be possible lock-free. But maybe I'm
>> wrong here and someone can give me an idea.
> 
> Perhaps a lock-free deque?

Maybe:

https://pdfs.semanticscholar.org/8a68/f45bd32ed050a96faa24139ab71178258f13.pdf

Its pretty glaringly.

[toc] | [prev] | [next] | [standalone]

#67519

>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>> look like? LRU-caches are only possible with doubly-linked lists.
>> So I thought this woudn't be possible lock-free. But maybe I'm
>> wrong here and someone can give me an idea.

> Perhaps a lock-free deque?

No, I want to move an arbitrary element of a doubly linked list
to the top.

[toc] | [prev] | [next] | [standalone]

#67520

On Saturday, 10 August 2019 12:42:22 UTC+3, Bonita Montero  wrote:
> >> Can anyone tell how a lock-free algorithm for a LRU-cache would
> >> look like? LRU-caches are only possible with doubly-linked lists.
> >> So I thought this woudn't be possible lock-free. But maybe I'm
> >> wrong here and someone can give me an idea.
> 
> > Perhaps a lock-free deque?
> 
> No, I want to move an arbitrary element of a doubly linked list
> to the top.

You anyway have some rainbow tree or hash table to find that
element that represents cached resource. The element being also
in linked list (having those prev/next pointers) is irrelevant
for consumers of cached resources. So you may leave the prev/next
pointers to be managed by single thread. When there is only single
thread that accesses those then task is "embarrassingly parallel"
IOW locks are not needed, IOW best "lock-free" there can be.

[toc] | [prev] | [next] | [standalone]

#67521

> You anyway have some rainbow tree or hash table to find that
> element that represents cached resource. The element being also
> in linked list (having those prev/next pointers) is irrelevant
> for consumers of cached resources. So you may leave the prev/next
> pointers to be managed by single thread. When there is only single
> thread that accesses those then task is "embarrassingly parallel"
> IOW locks are not needed, IOW best "lock-free" there can be.

No, the element is found by multiple threads accessing thr hashtable.
I think the buckets could be partitioned with each parition having
a single mutex; and te number of mutexes should be a fair multiple
of the number of HW-threads so there is a low likehood of a collision.
But each thread will push the found cache indivually to the top, so
there's no central thread doing this.
Intel's transactional memory incarnation RTM would be perfectly
suitable for that, also IBMs equivalent incarnation since the
POWE8-CPUs. But AMD-CPUs lack such a feature since they have this
bain-damaged exclusive cache-architecture betwen L1/L2 (both
inclusive) and L3 which doesn't allow this versioning which gets
the rollback from the L3-cache.

[toc] | [prev] | [next] | [standalone]

#67522

On Saturday, 10 August 2019 14:21:39 UTC+3, Bonita Montero  wrote:
> > You anyway have some rainbow tree or hash table to find that
> > element that represents cached resource. The element being also
> > in linked list (having those prev/next pointers) is irrelevant
> > for consumers of cached resources. So you may leave the prev/next
> > pointers to be managed by single thread. When there is only single
> > thread that accesses those then task is "embarrassingly parallel"
> > IOW locks are not needed, IOW best "lock-free" there can be.
> 
> No, the element is found by multiple threads accessing thr hashtable.
> I think the buckets could be partitioned with each parition having
> a single mutex; and te number of mutexes should be a fair multiple
> of the number of HW-threads so there is a low likehood of a collision.
> But each thread will push the found cache indivually to the top, so
> there's no central thread doing this.

But the threads could forward that task (of pushing the found element
to top) to single thread. It is technically management of those 
prev/next pointers that the cache users don't care about anyway.
Forwarding can be done for example by using lock-free deque and
so it is achieved that whole thing is entirely lock-free.
If it is not good enough for you then perhaps read the paper
that Chris M. Thomasson posted or search for similar.

> Intel's transactional memory incarnation RTM would be perfectly
> suitable for that, also IBMs equivalent incarnation since the
> POWE8-CPUs. But AMD-CPUs lack such a feature since they have this
> bain-damaged exclusive cache-architecture betwen L1/L2 (both
> inclusive) and L3 which doesn't allow this versioning which gets
> the rollback from the L3-cache.

Processor cache architecture is mostly abstracted out of reach on
level of C++. We can adjust the behavior of our software a bit
and rest of it ... is topical in comp.arch.

[toc] | [prev] | [next] | [standalone]

#67523

> But the threads could forward that task (of pushing the found
> element to top) to single thread. It is technically management
> of those prev/next pointers that the cache users don't care
> about anyway. ...

That would be totally brain-damaged because locking the linked
list and pushing the list-entry to the top by the thread that
accesses a certain block and thereby attributing it at the most
recent block would be more efficient. That's just because the
blocks aren't managed by a single thread but they're touched
shared.

> Processor cache architecture is mostly abstracted out of reach
> on level of C++. We can adjust the behavior of our software a
> bit and rest of it ... is topical in comp.arch.

Hey, transactional memory was one of the candidate-topics for C++20!
And the HLE-flavor of transactional memory which Intel implemnts (and
I recenctly wonderted that IBM implemented the same since the POWER8)
perfectly fits with the usual mutex-locking of C++. It's just that
HLE is more appropriate with mutex-locking with a small scope - like
in this example.

[toc] | [prev] | [next] | [standalone]

#67531

On Saturday, 10 August 2019 16:52:12 UTC+3, Bonita Montero  wrote:
> > But the threads could forward that task (of pushing the found
> > element to top) to single thread. It is technically management
> > of those prev/next pointers that the cache users don't care
> > about anyway. ...
> 
> That would be totally brain-damaged because locking the linked
> list and pushing the list-entry to the top by the thread that
> accesses a certain block and thereby attributing it at the most
> recent block would be more efficient.

A brain has to be rather calcified to receive total damage from
simple idea how to get rid of constant race over top of list.

[toc] | [prev] | [next] | [standalone]

#69475

On 8/10/2019 9:40 AM, Öö Tiib wrote:
> On Saturday, 10 August 2019 16:52:12 UTC+3, Bonita Montero  wrote:
>>> But the threads could forward that task (of pushing the found
>>> element to top) to single thread. It is technically management
>>> of those prev/next pointers that the cache users don't care
>>> about anyway. ...
>>
>> That would be totally brain-damaged because locking the linked
>> list and pushing the list-entry to the top by the thread that
>> accesses a certain block and thereby attributing it at the most
>> recent block would be more efficient.
> 
> A brain has to be rather calcified to receive total damage from
> simple idea how to get rid of constant race over top of list.
> 

Indeed the head is lock-free!

[toc] | [prev] | [next] | [standalone]

#69476

>> That would be totally brain-damaged because locking the linked
>> list and pushing the list-entry to the top by the thread that
>> accesses a certain block and thereby attributing it at the most
>> recent block would be more efficient.

> A brain has to be rather calcified to receive total damage from
> simple idea how to get rid of constant race over top of list.

Then tell me that simple idea no one published before.

[toc] | [prev] | [next] | [standalone]

#67604

I just found this article:
https://en.wikipedia.org/wiki/Page_replacement_algorithm
It it a good starting-point for this issue.

[toc] | [prev] | [next] | [standalone]

#67608

On 8/8/2019 11:59 PM, Bonita Montero wrote:
> Can anyone tell how a lock-free algorithm for a LRU-cache would
> look like? LRU-caches are only possible with doubly-linked lists.
> So I thought this woudn't be possible lock-free. But maybe I'm
> wrong here and someone can give me an idea.

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.

[toc] | [prev] | [next] | [standalone]

#67614

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

[toc] | [prev] | [next] | [standalone]

#67634

On 8/13/2019 1:24 AM, Bonita Montero wrote:
>> 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.

Yeah. It would boil down to a single head.

For some reason I am thinking about a lock-free LIFO as the head. 
Humm... Thinking. Working on some other stuff right now, but there seems 
like a way to do this.

[toc] | [prev] | [next] | [standalone]

#67635

On 8/13/2019 11:51 PM, Chris M. Thomasson wrote:
> On 8/13/2019 1:24 AM, Bonita Montero wrote:
>>> 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.
> 
> Yeah. It would boil down to a single head.

A page is touched, then instantly pushed onto the active lock-free LIFO. 
Marked as logically removed, yet still exists. Can be moved later. 
Humm... I have not worked on lock-free in a while. But might be able to 
sketch out a strange thing on this.


> 
> For some reason I am thinking about a lock-free LIFO as the head. 
> Humm... Thinking. Working on some other stuff right now, but there seems 
> like a way to do this.

[toc] | [prev] | [next] | [standalone]

#67615

> It is a simple deadlock free hashed mutex algorihtm.

BTW: Your hashing could be cleverer.
With ...
    return (std::size_t)(((ptr_uint << 9) * 103) % m_locks.size());
... you multiply ptr_uint by 52.736. That's not a good hash-function.
Better mutitply by the largest prime fitting in a size_t. You can
get them here: https://primes.utm.edu/lists/2small/
So the maximum prime for 32 bit size_t would be 0xFFFFFFFB, the
maximum prime for 64 bit would be 18.446.744.073.709.551.557 (my
calculator can't convert that to hex).

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.c++

csiph-web