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

Groups > sci.math > #641539

String interning is HashSet and not HashMap (Was: Linux kernel's RCU-protected hash tables)

Cross-posted to 3 groups.

Show all headers | View raw

Hi,

The Linux kernel's RCU-protected hash tables
is still not free of problems. Multiple writers
might still need extra work.

String interning with a HashSet (no values, just keys)
is actually easier to make lock-free without full
CAS because you're only concerned with existence,

not updates.

Bye

P.S.: I am not affected by this amplified nonsense.
Dogelog Player has even no atom table. And since it
is single threaded, the HashMap for predicate lookup

is totally lock free. It is single threaded and it
has cooperative multithreading. Internally it uses
async/await from JavaScript for example, which is

a cooperative multthreading approach, but from the
outside it provides tasks and sleep and stuff.
Recently demonstrated a little Strudel style music coding:

Strudel Coding in Dogelog Player
https://medium.com/2989/bbb9c78fcd67

In basically declared multi-threading dead, before
AI accelerators were there. I had more some worker
things in mind, with more thorough siloing and isolation.

But now that we have AI accelerators, the decision
to abandon multithreadinhg looks even more splendid.

Mild Shock schrieb:
> 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