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

Groups > sci.math > #641537

Linux kernel's RCU-protected hash tables (Re: Algorithm introduced in Hogwild! SGD (Niu et al., 2011))

Cross-posted to 3 groups.

Show all headers | View raw

Hi,

An example of a lock free datastructure, that
even doesn't use CAS, is for example:

Read-Copy-Update (RCU) Based Hash Tables
These use only memory barriers/fences and atomic pointer writes:
- Basic approach: Readers access the table without locks,
   writers create new versions
- Memory reclamation: Uses RCU grace periods instead of CAS
- Example: Linux kernel's RCU-protected hash tables
- Operations: Only requires atomic loads/stores and memory barriers

For Prolog systems there are also various
approaches arround, if one aims at the multi-threading
model for dynamic databass or atom tables.

I think this multi-threading model should be
abadoned, in favor of things that can be speed
up by a AI accelerator. Dogelog Player has abandoned

multi-threading all together. But for example
SWI-Prolog has heavily focused on lock free
data structures already like 10 years ago,

and it seems YAP can still not keep up with
SWI-Prolog. See for example here:

Yet Another Lock-Free Atom Table Design
for Scalable Symbol Management in Prolog
https://link.springer.com/article/10.1007/s10766-024-00766-z

But in my opinion, in the light of the AI Boom,
this is all amplified nonsense.

Bye

Mild Shock schrieb:
> Hi,
> 
> What are you, a 5 year old moron?
> 
> There are millions of algorithm that use volatile
> variables. Just look at the Java code base.
> 
> But I was not refering to multi-threading, I
> was refering to PRAM for matrix operations.
> 
> See for example here:
> 
> Hogwild!: A Lock-Free Approach to
> Parallelizing Stochastic Gradient Descent
> https://arxiv.org/pdf/1106.5730
> 
> Fuck off moron.
> 
> Bye
> 
> Blending Molostvov schrieb:
>> Mild Shock wrote:
>>
>>> What are you, a 5 year old moron?
>>>
>>> Pascual Sokolsky schrieb:
>>>> Mild Shock wrote:
>>>>
>>>>> But in principle the architecture is rather:
>>>>>
>>>>> parallel random-access machine (parallel RAM or PRAM) is a
>>>>> shared-memory abstract machine.
>>>>> https://en.wikipedia.org/wiki/Parallel_RAM
>>>>>
>>>>> The above class of machines is not widely know.
>>>>> But PRAM has been also studied, already in the 80's.
>>>>
>>>> parallel read of shared memory is only allowed to cia and the chinese
>>>> governoment; must be somenthing you dont know
>>
>> from shared memory you only read and write sequential, me frendo,
>> driven by semaphores, atomic instructions and so on. You are not that
>> fucking stupid to write parallel to a cell, are you
>>
> 

Back to sci.math | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Pascual Sokolsky <aoa@ssppsc.pl> - 2025-12-01 19:58 +0000
  Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 21:17 +0100
    Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Blending Molostvov <noo@biiooe.ru> - 2025-12-01 20:44 +0000
      Algorithm introduced in Hogwild! SGD (Niu et al., 2011) (Re: parallel random-access machine) Mild Shock <janburse@fastmail.fm> - 2025-12-01 22:06 +0100
        Linux kernel's RCU-protected hash tables (Re: Algorithm introduced in Hogwild! SGD (Niu et al., 2011)) Mild Shock <janburse@fastmail.fm> - 2025-12-01 22:26 +0100
          String interning is HashSet and not HashMap (Was: Linux kernel's RCU-protected hash tables) Mild Shock <janburse@fastmail.fm> - 2025-12-01 22:40 +0100
        Re: Algorithm introduced in Hogwild! SGD (Niu et al., 2011) (Re: parallel random-access machine) Bosephis Otlesnov <ooiv@th.ru> - 2025-12-01 21:42 +0000
          POINT OF VIEW OF AN ALGORITHM (Re: Algorithm introduced in Hogwild! SGD (Niu et al., 2011)) (Re: parallel random-access machine) Mild Shock <janburse@fastmail.fm> - 2025-12-01 23:12 +0100
            Introduction to AMBA® 4 ACE™ (2011) (Was: POINT OF VIEW OF AN ALGORITHM) Mild Shock <janburse@fastmail.fm> - 2025-12-01 23:37 +0100
              Sputnik Schock: Academia is Disposable [I. J. Good Ultraintelligence] (Was: Introduction to AMBA® 4 ACE™ (2011)) Mild Shock <janburse@fastmail.fm> - 2025-12-01 23:53 +0100
              Re: Introduction to AMBA® 4 ACE™ (2011) (Was: POINT OF VIEW OF AN ALGORITHM) Josbanne Balagula <ajbn@oll.ru> - 2025-12-01 23:06 +0000
                Re: Introduction to AMBA® 4 ACE™ (2011) (Was: POINT OF VIEW OF AN ALGORITHM) Mild Shock <janburse@fastmail.fm> - 2025-12-02 00:08 +0100

csiph-web