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

Groups > comp.lang.prolog > #14744

Cache-Trashing vs Cache-Friendly [Code Example] (Re: Do it like in acyclic_decompose/3)

Show all headers | View raw

 > Write operation are sometimes
 > poison for the CPU and the RAM.

Try this where SIZE is a prime number:

/* Cache-Trashing Example */
void column_major_access() {
     for (int col = 0; col < SIZE; col++) {
         for (int row = 0; row < SIZE; row++) {
             matrix[row][col] += 1;
         }
     }
}

/* Cache-Friendly Example */
void row_major_access() {
     for (int row = 0; row < SIZE; row++) {
         for (int col = 0; col < SIZE; col++) {
             matrix[row][col] += 1;
         }
     }
}


Mild Shock schrieb:
> Hi,
> 
> Interstingly there is an obvious way how
> to do it without a braching association list,
> that has different futures so to speack,
> 
> the below code repeatedly generates
> dfferent association lists via [X|S].
> We could of course instead do a threading
> 
> of the association list through some predicate,
> and use some state on each entry inside the
> association list, similar like in acyclic_decompose/3
> 
> we used a threading and entry state.
> 
> Bye
> 
> Mild Shock schrieb:
>> Hi,
>>
>> So the 115 ms by Dogelog Player are faster than the
>> 0.130s by Scryer Prolog. Quite amazing! From
>> Dogelog Player library(math):
>>
>> /**
>>   * acyclic_term(T): [TC2 8.3.11]
>>   * The predicate succeeds when the Prolog term T is an acyclic term,
>>   * otherwise the predicate fails.
>>   */
>> % acyclic_term(+Term)
>> acyclic_term(X) :- sys_cyclic_term(X, []), !, fail.
>> acyclic_term(_).
>>
>> % sys_cyclic_term(+Term, +List)
>> sys_cyclic_term(X, S) :- compound(X),
>>     member(Y, S),
>>     same_term(X, Y), !.
>> sys_cyclic_term(X, S) :- compound(X),
>>     X =.. [_|L],
>>     member(Y, L),
>>     sys_cyclic_term(Y, [X|S]).
>>
>> Algorithms that implicitly detect sharing cannot
>> do much? Since we only need to find a first cycle?
>> Also a challenge to bring the association list to
>> native and lets say turn it into a hash table,
>>
>> don't know yet when and how even somebody would
>> attempt that. Big advantage of anything not using
>> Deutsch-Schorr-Waite , no write operation into the
>> given term. Write operation are sometimes
>>
>> poison for the CPU and the RAM.
>>
>> Bye
>>
>> Mild Shock schrieb:
>>> Hi,
>>>
>>> Assume that we live in a world where we
>>> have excess memory. So we can afford stacks!
>>> And then make the crucial observation,
>>>
>>> we can use the stack of the Prolog engine,
>>> no need to create an artificial stack in C,
>>> or use the native stack of C.
>>>
>>> I guess SWI-Prolog has already groked the
>>> first we can "afford stacks". But did anybody
>>> already grok the "100% Prolog" idea?
>>>
>>> Well we are not yet there 100% Prolog
>>> has still an overhead. Here is a little
>>> test acyclic_term/2:
>>>
>>> /* SWI-Prolog 9.3.26, C Stacks and/or Agendas */
>>> ?- time((between(1,30,_), acyclic2, fail; true)).
>>> % 330,150 inferences, 0.016 CPU in 0.023 seconds
>>> (69% CPU, 21129600 Lips)
>>> true.
>>>
>>> /* Trealla Prolog 2.79.6, ?? */
>>> ?- time((between(1,30,_), acyclic2, fail; true)).
>>> % Time elapsed 0.063s, 643413 Inferences, 10.166 MLips
>>>     true.
>>>
>>> /* Dogelog Player 1.3.5, 100% Prolog */
>>> ?- time((between(1,30,_), acyclic2, fail; true)).
>>> % Zeit 115 ms, GC 0 ms, Lips 11803904, Uhr 28.07.2025 10:03
>>> true.
>>>
>>> /* Scryer Prolog 0.9.4-417, Deutsch-Schorr-Waite  */
>>> ?- time((between(1,30,_), acyclic2, fail; true)).
>>> % CPU time: 0.130s, 626_829 inferences
>>> true.
>>>
>>> Bye
>>
> 

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Novacore goes Bisimulation: Scryer Prolog is Slow! Mild Shock <janburse@fastmail.fm> - 2025-07-25 13:51 +0200
  Is Mild Shock going rogue? (Was: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:07 +0200
    Is Mostowski Collapse a professional mathematician (Was: Is Mild Shock going rogue?) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:16 +0200
      New Project Name: NovaCore becomes VibeCore (Re: Is Mostowski Collapse a professional mathematician) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:42 +0200
  Nice Printing Error Scryer Prolog (Was: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-26 21:33 +0200
    Dynamic unify_with_occurs_check/2 speed-up (Was: Nice Printing Error Scryer Prolog) Mild Shock <janburse@fastmail.fm> - 2025-07-26 21:37 +0200
  The End of Deutsch-Schorr-Waite [cycle_detection.rs] (Was: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-28 10:50 +0200
    Backtracking Branching Association List (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-07-28 11:02 +0200
      Do it like in acyclic_decompose/3 (Re: Backtracking Branching Association List) Mild Shock <janburse@fastmail.fm> - 2025-07-28 11:38 +0200
        Cache-Trashing vs Cache-Friendly [Code Example] (Re: Do it like in acyclic_decompose/3) Mild Shock <janburse@fastmail.fm> - 2025-07-28 17:27 +0200
    Entering the Age of Rational Trees (2025) (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-08-16 13:02 +0200
    The End of Debray Allocator (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-08-24 14:44 +0200
  The pairs are nasty, otherwise not always slow! (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-30 14:45 +0200
    It was painful for my GC, but fixed now (Re: The pairs are nasty, otherwise not always slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-30 14:51 +0200
  Scryer Prolog has the most useless max_depth (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-08-02 13:43 +0200
    Novacore goes native (=)/2 and (==)/2 bisimulation (Was: Scryer Prolog has the most useless max_depth) Mild Shock <janburse@fastmail.fm> - 2025-08-02 14:45 +0200

csiph-web