[Oberon] ... MOD 65536

[Hans Klaver]

I put a global counter in the conditional part of Trees, and indeed it reveals that this part is entered only 2 times of the 10 calls, as you predicted.

It's interesting that the "reference output" of Trees is the first ten integers shown here:
https://github.com/microsoft/test-suite/blob/master/SingleSource/Benchmarks/Stanford/Treesort.reference_output <https://github.com/microsoft/test-suite/blob/master/SingleSource/Benchmarks/Stanford/Treesort.reference_output>

giving at least me the illusion that the Tree benchmark was run correctly 10 times. 

Now that I look more carefully this is just an illusion, because this "reference output" is reusing the global array sortlist, which is the list of unsorted integers and which is left unchanged after each run of Trees. So this is not a well chosen reference output, asserting only a correct initialization of this array. A least the number of times the procedure CheckTree is called should be reported as well.

For the time being (until I have crafted my private garbage collector ;-) within Oberon System V5 I will run the Tree benchmark only once or twice at a time.

Once again, thanks for your educational help and advice!

--
Hans

> Op 13 apr. 2020, om 21:09 heeft Joerg <joerg.straube at iaeth.ch> het volgende geschreven:
> 
> Separate module or not, is not the key question. It does not help much. 
> As it is coded today (sort 5000 elements) Trees needs (worst case scenario) 160 kB heap space.
> The Oberon system having only a total amount of 1MB offers ~420 kB heap space. So, it is impossible to run the algorithm 10 times.
> 
> The garbage collector freeing up unused heap space is programmed in module Oberon but it‘s not exported. So officially, you can’t run the GC while your program runs. The allocated and now unused memory is only collected AFTER the Hennessy terminates.
> 
> With a little bit of trickery you could program your own garbage collector that frees up all data structure Trees allocated with NEW after every call of Trees. But this is a little far fetched...
> 
> br
> Jörg
> 
>> Am 13.04.2020 um 20:36 schrieb Hans Klaver <hklaver at dds.nl>:
>> 
>> Ah, now I see. 
>> 
>> So my current implementation of the Tree benchmark in Hennessy.Mod is not correct, and is 'cheating'.
>> 
>> Maybe I should isolate the Tree benchmark as a separate module. This is also done in the C versions of the LLVM test-suite (for all benchmarks of the suite). And I suspect that the original Pascal versions of the Hennessy benchmarks also were separate programs, but I have never seen them.
>> 
>> --
>> Hans
>> 
>> 
>>> Op 13 apr. 2020, om 20:15 heeft Joerg <joerg.straube at iaeth.ch <mailto:joerg.straube at iaeth.ch>> het volgende geschreven:
>>> 
>>> Hans
>>> 
>>> That „Trees“ seems to run faster is because I skip the execution if there is not enough memory.
>>> 
>>> In other words, although Time() calls every algorithm 10 times, Trees will in a lot of cases only run 2 or 3 times (of those 10 calls) depending on the amount of heap space left...
>>> 
>>> br
>>> Jörg
>>> 
>>>> Am 13.04.2020 um 19:47 schrieb Hans Klaver <hklaver at dds.nl <mailto:hklaver at dds.nl>>:
>>>> 
>>>> Hi Jörg,
>>>> 
>>>> Just now I noticed that my reply to your modification of Hennessy.Trees (below) did not make it to the list (possibly because I included a few screenprints of run times). 
>>>> 
>>>> So now again:
>>>> 
>>>> Thanks Jörg, this modification is great! 
>>>> Everything runs as it should now.
>>>> 
>>>> Now also in Oberon System V5 Hennessy.Mod can be used with ...MOD 65536 (sic!) in procedure Rand.
>>>> All reference output is as it should be.
>>>> 
>>>> And as a nice side effect of your modification the treesort benchmark runs nearly three times as fast as before:
>>>> 
>>>> Run times Hennessy Mm and Sort procedures in V5 (10 runs, ms):
>>>> 
>>>> MOD     Trees     Intmm  Mm   Quick Bubble  Tree
>>>> 65535   original   983   998   900   2016   747
>>>> 65536   original   984  1016   933   2017   --
>>>> 
>>>> 65535   modified   966  1014   876   1954   647
>>>> 65536   modified   970  1016   908   1971  *259*
>>>> 
>>>> These are all benchmarks that make use of procedure Rand. As can be seen in most of them there is no noticable difference whether 65535 of 65536 is used in the MOD expression, but sometimes there can be a huge difference. 
>>>> 
>>>> This is an illustration that in benchmarks it is important to consistently use the same pseudo-random generator and initial seed.
>>>> 
>>>> --
>>>> Hans Klaver
>>>> 
>>>> 
>>>>> Op 10 apr. 2020, om 13:20 heeft Jörg <joerg.straube at iaeth.ch <mailto:joerg.straube at iaeth.ch>> het volgende geschreven:
>>>>> 
>>>>> Hans
>>>>>  
>>>>> I did the following:
>>>>> PROCEDURE Trees* ();
>>>>>                 VAR i : LONGINT;
>>>>>                 BEGIN
>>>>>                                IF Kernel.heapLim - Kernel.heapOrg - Kernel.allocated > 160000 THEN
>>>>>                                                tInitarr();
>>>>>                                                NEW(tree); 
>>>>>                                                (* here the rest of Trees *)
>>>>>                                END;
>>>>>                                tree := NIL; Oberon.Collect(0) (* tell the GC to start after Hennessy terminated *)
>>>>>                 END Trees;
>>>>>  
>>>>> With these modifications you can take whatever random number generator you wanna use.
>>>>> DIV 65535 (wrong) or DIV 65536 (corresponds to the C original) or any other.
>>>>>  
>>>>> br
>>>>> Joerg

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20200413/aa7a4fe4/attachment.html>