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

Groups > comp.lang.prolog > #15084

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 comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

What is analog computing nowadays? (Re: An old Busy Beaver ASIC (Application-Specific Integrated Circuit) (Was: Could AlphaEvolve find the sixth busy beaver ?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 11:25 +0100
  Wake-up call until everybody gets ear-bleeding (Re: What is analog computing nowadays?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 12:01 +0100
    BB(745) is independent of ZFC (Was: Wake-up call until everybody gets ear-bleeding) Mild Shock <janburse@fastmail.fm> - 2025-12-01 12:07 +0100
      Write ZFC formulas on a tape (of a Turing machine) (Re: BB(745) is independent of ZFC ) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:18 +0100
        Turing machines have neurons (Re: Write ZFC formulas on a tape (of a Turing machine)) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:19 +0100
          A logical calculus in nervous activity [McCulloch & Pitts 1943] (Re: Turing machines have neurons) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:20 +0100
            Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943]) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:39 +0100
            Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943]) Mild Shock <janburse@fastmail.fm> - 2025-12-02 17:43 +0100
              Re: Busy Beaver and Theory Consistency (Was: A logical calculus in nervous activity [McCulloch & Pitts 1943]) Mild Shock <janburse@fastmail.fm> - 2025-12-02 23:18 +0100
  Re: What is analog computing nowadays? (Re: An old Busy Beaver ASIC (Application-Specific Integrated Circuit) (Was: Could AlphaEvolve find the sixth busy beaver ?) Maciej Woźniak <mlwozniak@wp.pl> - 2025-12-01 12:09 +0100
    parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Mild Shock <janburse@fastmail.fm> - 2025-12-01 12:15 +0100
      Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Maciej Woźniak <mlwozniak@wp.pl> - 2025-12-01 13:23 +0100
        Nope, you can't, because of the CRCW instuction (Was: parallel random-access machine) Mild Shock <janburse@fastmail.fm> - 2025-12-01 17:12 +0100
          Algorithm introduced in Hogwild! SGD (Niu et al., 2011) (Was: Nope, you can't, because of the CRCW instuction) Mild Shock <janburse@fastmail.fm> - 2025-12-01 17:31 +0100
            PRAMs might be closer to physics: Boltzman machines, etc.. (Was: Algorithm introduced in Hogwild! SGD) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:02 +0100
          Re: Nope, you can't, because of the CRCW instuction (Was: parallel random-access machine) Maciej Woźniak <mlwozniak@wp.pl> - 2025-12-01 17:59 +0100
            PRAMs might be closer to physics: Boltzman machines, etc.. (Re: Nope, you can't, because of the CRCW instuction) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:05 +0100
            PRAMs might be closer to physics: Boltzman machines, etc.. (Re: Nope, you can't, because of the CRCW instuction) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:08 +0100
              Physics more difficult than Rasperry LED cube? (Was: PRAMs might be closer to physics: Boltzman machines, etc..) Mild Shock <janburse@fastmail.fm> - 2025-12-01 18:25 +0100
        Re: parallel random-access machine (parallel RAM or PRAM (Was: What is analog computing nowadays?) Thomas Heger <ttt_heg@web.de> - 2025-12-03 07:17 +0100
          Re: parallel random-access machine (parallel RAM or PRAM (Was: What is  analog computing nowadays?) Python <python@cccp.invalid> - 2025-12-03 06:46 +0000
          Re: parallel random-access machine (parallel RAM or PRAM) Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2025-12-03 08:02 +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
      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

csiph-web