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 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#67616

Am 13.08.2019 um 10:42 schrieb Bonita Montero:
> ...
> 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).

So finally it is 0xffffffffffffffc5.

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

#67617

On 13.08.19 11:19, Bonita Montero wrote:
> Am 13.08.2019 um 10:42 schrieb Bonita Montero:
>> ...
>> 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).
> 
> So finally it is 0xffffffffffffffc5.

echo "obase=16; 18446744073709551557" | bc

Josef

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

#67618

> Better mutitply by the largest prime fitting in a size_t. ...

I forgot that this is a rule only if this prime isn't
a meresenne-prime. If it is, take the next lower one.

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

#67630

On 8/13/2019 1:42 AM, Bonita Montero wrote:
>> It is a simple deadlock free hashed mutex algorihtm.
> 
> BTW: Your hashing could be cleverer.

Big Time! yikes.


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

Yes. indeed. When I was coding my algorihtm, well, just used a stupid 
simple hash of a pointer address. The posted version is in an embryonic, 
example state.

Actually, the algorihtm can be used as a lock-based STM. It can use 
try_locks to detect conflict and try to do something else before it 
actually blocks on a mutex within the main table. So, it can be combined 
with a lock-free TM. Use the locks as needed. Wrt the slowpath, or for 
fallback conditions.

Funny thing, since it is based on hashing pointer addresses, well, each 
run of the same program can use different locks each time. If the OS 
randomizes where the program can get its memory from. Pointer A, run 1 
is different in "value" of Pointer A, run 2.

;^)

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

#67631

On 8/13/2019 3:03 PM, Chris M. Thomasson wrote:
> On 8/13/2019 1:42 AM, Bonita Montero wrote:
>>> It is a simple deadlock free hashed mutex algorihtm.
>>
>> BTW: Your hashing could be cleverer.
> 
> Big Time! yikes.
> 
> 
>> 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).
> 
> Yes. indeed. When I was coding my algorihtm, well, just used a stupid 
> simple hash of a pointer address. The posted version is in an embryonic, 
> example state.

The hash needs to try and avoid collisions. Each collision, wrt 
different pointers mapping into the same mutex, well, that is BAD.


> 
> Actually, the algorihtm can be used as a lock-based STM. It can use 
> try_locks to detect conflict and try to do something else before it 
> actually blocks on a mutex within the main table. So, it can be combined 
> with a lock-free TM. Use the locks as needed. Wrt the slowpath, or for 
> fallback conditions.
> 
> Funny thing, since it is based on hashing pointer addresses, well, each 
> run of the same program can use different locks each time. If the OS 
> randomizes where the program can get its memory from. Pointer A, run 1 
> is different in "value" of Pointer A, run 2.
> 
> ;^)
> 

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

#67632

On 8/13/2019 3:03 PM, Chris M. Thomasson wrote:
> On 8/13/2019 1:42 AM, Bonita Montero wrote:
>>> It is a simple deadlock free hashed mutex algorihtm.
>>
>> BTW: Your hashing could be cleverer.
> 
> Big Time! yikes.
[...]
> Funny thing, since it is based on hashing pointer addresses, well, each 
> run of the same program can use different locks each time. If the OS 
> randomizes where the program can get its memory from. Pointer A, run 1 
> is different in "value" of Pointer A, run 2.

Sorry for the message flood, but, failed try_locks can be used to build 
meta data about how the table of mutexes is being used over time.

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

#68627

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

I've found a solution that is mega-cool. I'm not gonna reveal it
because I'm thinking about to get an US-patent on it, but it is a
exotic combination of locked and lock-free programming. It scales
almost linear with the number of threads.

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

#68628

Bonita Montero <Bonita.Montero@gmail.com> claims:
>>  LRU-caches are only possible with doubly-linked lists.

Hm. That's news, indeed.  Have you produced a formal proof?

You may want to consider LRU cache replacement algorithms used
in processor caches.

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

#68629

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

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

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

#68634

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.

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

#68632

On 9/24/2019 9:33 AM, 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.
> 
> I've found a solution that is mega-cool. I'm not gonna reveal it
> because I'm thinking about to get an US-patent on it, but it is a
> exotic combination of locked and lock-free programming. 

Do a deep patent feasibility study! Build a list of as many references 
as you can, and read them all. It can safe you some of your hard earned 
$$$. Patent lawyers cost a lot money! Or, do you work for Microsoft? For 
some reason, I thought about that.

Let me guess... Clever hashed locking for the slow-paths, and lock-free 
for the fast paths? That is a basic idiom. RCU uses it a lot. Locks for 
the writers and sync free for the readers. The readers do not use any 
atomics or memory barriers at all. Well, Alpha aside for a moment...

Here is a very simple example of a mixture of lock-based and wait-free. 
100% wait-free on the push side, and "sometimes" lock-based on the 
reader side experimental LIFO:

https://groups.google.com/d/msg/comp.arch/8Y0C8zGjtqI/bwg-hBLRAQAJ



> It scales
> almost linear with the number of threads.

Cool!

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

#68633

On 9/24/2019 1:50 PM, Chris M. Thomasson wrote:
> On 9/24/2019 9:33 AM, Bonita Montero wrote:
[...]
> Let me guess... Clever hashed locking for the slow-paths, and lock-free 
> for the fast paths? That is a basic idiom. RCU uses it a lot. Locks for 
> the writers and sync free for the readers. The readers do not use any 
> atomics or memory barriers at all. Well, Alpha aside for a moment...
> 
> Here is a very simple example of a mixture of lock-based and wait-free. 
> 100% wait-free on the push side, and "sometimes" lock-based on the 
> reader side experimental LIFO:
> 
> https://groups.google.com/d/msg/comp.arch/8Y0C8zGjtqI/bwg-hBLRAQAJ

The experimental core of the code above is:
________________________________________
// A work node
struct ct_work
{
      std::atomic<ct_work*> m_next;
      std::thread::id m_data;
      ct_work(std::thread::id data) : m_next(nullptr), m_data(data) {}


      void process()
      {
          // [...]
          // User Processing For This Work
      }


      ct_work* get_next() const
      {
          ct_work* w = nullptr;

          while ((w = m_next.load(CT_MB_RLX)) == CT_WAIT)
          {
              // we can spin, or even do other work right here...
              std::this_thread::yield();
          }

          return w;
      }
};

// Easy Stack, only uses XCHG
struct ct_estack
{
      std::atomic<ct_work*> m_head;
      ct_estack() : m_head(nullptr) {}


      void push(ct_work* n)
      {
          n->m_next.store(CT_WAIT, CT_MB_RLX);
          ct_work* head = m_head.exchange(n, CT_MB_REL); // release
          n->m_next.store(head, CT_MB_RLX);
      }


      ct_work* flush_try()
      {
          return m_head.exchange(nullptr, CT_MB_ACQ); // acquire
      }
};



// Consume an Easy Stack...
void ct_consume(
      ct_estack& estack
) {
      ct_work* w = estack.flush_try();

      while (w)
      {
          // Process FIRST!
          w->process();

          // Now, we can gain the next pointer.
          ct_work* next = w->get_next();

          // Okay, we can delete the work
          delete w;
          g_allocs.fetch_sub(1, CT_MB_RLX); // dec

          w = next;
      }
}
________________________________________


The takeaway is that the LIFO class ct_estack only uses XCHG, and no 
loops. Now, this can be distributed.

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

#69249

> https://groups.google.com/d/msg/comp.arch/8Y0C8zGjtqI/bwg-hBLRAQAJ

A lock-free stack is the simplest kind of lock-free algorithm.

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.

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

#69251

> A lock-free stack is the simplest kind of lock-free algorithm.
> 
> 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.

BTW: The drop from four to fife threads is because of the stupid CCX
-concept of my old Ryzen 7 1800X. On this CPU the cores are grouped in
clusters of four cores. Within such a cluster communications is faster
than between the groups. And the rest of the slowdown wih increasing
number of threads simply comes from the cache-traffic.
The leftmost bar in each group is the bar with parameter zero, where
my algorithm has almost the same locking-behaviour like having a single
global lock for everything. As you can see, there's a significant drop
from group 1 / bar 1 to group 2 / bar 1. But the drop isn't as dramatic
as it might look because I simulate a typical behaviour of filesystems
and databases: multiple fetches from the hash-table / LRU-list occur
at once because of prefetching. So my class has a call for getting
some entries in a row where the locks have been taken only once.
Without prefetching you get this performance:
https://abload.de/image.php?img=performance2b2j3l.png
One interesting thing here is that the simple one-mutex-for-all-algo
has a significant advantage over with mine when run single-threaded.
When I raise the parameter which helps my algorithm to handle mt-work-
loads, the performance even drops single-threaded! The other bars in
this group are also single-threaded but have an increasing parameter
to handle multithreaded access. And now as we don't have any prefet-
ching here look at the first bars in each group; that are the bars
of the one-mutex-for-all-case. The drop is even higher than 1 : 50
through the synch-overhead.
For larger number of threads the role of the optimization-parameter
beomes increasingly important. The group shifts more and more to be
a leftmost part of a logarithmic curve.

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

#69258

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.

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

#68637

Bonita Montero <Bonita.Montero@gmail.com> wrote:
> I've found a solution that is mega-cool. I'm not gonna reveal it
> because I'm thinking about to get an US-patent on it, but it is a
> exotic combination of locked and lock-free programming. It scales
> almost linear with the number of threads.

I don't think you can patent algorithms even in the US currently.
They got rid of that loophole.

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

#68638

> I don't think you can patent algorithms even in the US currently.
> They got rid of that loophole.

There's no loophole. You can officially patent algorithms in the US.

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

#68647

Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I don't think you can patent algorithms even in the US currently.
>> They got rid of that loophole.
> 
> There's no loophole. You can officially patent algorithms in the US.

"Allvoice Developments US, LLC v. Microsoft Corp., 612 F. App'x 1009
(Fed. Cir. 2015). The Supreme Court had held previously that software
in algorithm form without machine implementation could not be patented
in process format, see Gottschalk v. Benson and Parker v. Flook, but
could be patented when claimed as a machine inventively using software,
see Diamond v. Diehr."

https://en.wikipedia.org/wiki/Software_patents_under_United_States_patent_law

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

#68651

>> There's no loophole. You can officially patent algorithms in the US.

> "Allvoice Developments US, LLC v. Microsoft Corp., 612 F. App'x 1009
> (Fed. Cir. 2015). The Supreme Court had held previously that software
> in algorithm form without machine implementation could not be patented
> in process format, see Gottschalk v. Benson and Parker v. Flook, but
> could be patented when claimed as a machine inventively using software,
> see Diamond v. Diehr."

Look, here, that's a similar patent to what we're talking about:
https://patents.google.com/patent/US5778442

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

#68652

Bonita Montero <Bonita.Montero@gmail.com> stubbornly removed Juha Nieminen <nospam@thanks.invalid> attribution

>>> There's no loophole. You can officially patent algorithms in the US.
>
>> "Allvoice Developments US, LLC v. Microsoft Corp., 612 F. App'x 1009
>> (Fed. Cir. 2015). The Supreme Court had held previously that software
>> in algorithm form without machine implementation could not be patented
>> in process format, see Gottschalk v. Benson and Parker v. Flook, but
>> could be patented when claimed as a machine inventively using software,
>> see Diamond v. Diehr."
>
>Look, here, that's a similar patent to what we're talking about:
>https://patents.google.com/patent/US5778442
>

My most recent patent (Issued 9/27/2019) is numbered 10,394,730.   Your
referenced patent was granted over twenty years ago, long before the
court case Juha has referenced.

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

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

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

csiph-web