[luatex] how many bytes for fontdimens?

[jfbu]

> Le 3 août 2021 à 12:49, Hans Hagen <j.hagen at xs4all.nl> a écrit :
> 
> On 8/3/2021 9:45 AM, jfbu wrote:
>> Hi,
>>> Le 3 août 2021 à 09:09, Hans Hagen <j.hagen at xs4all.nl <mailto:j.hagen at xs4all.nl>> a écrit :
>>> 
>>> On 8/2/2021 9:37 PM, jfbu wrote:
>>>> forgot to mention that I am aware a \fontdimen is limited to 2**30 strictly anyhow
>>>> but my question is whether such « arrays » are stored 32bits or 64bits itemwise
>>> it happens to be an array of 32 bit integers (that grows on demand) but such implementaiton details are unspecified (could as well have been a sparse array in which case each entry that is actually set has more
>>> 
>>> also, the fact that it grow is a sort of side effect of the fact that tfm fonts can have 7 or more, but 7 are used, for text upto more for math fonts
>>> 
>>> so, i wouldn't rely on these properties too much
>> Thanks!
>> Reason I asked is because I contributed an Eratosthenes Prime sieve to a github site comparing a whole bunch of langages and it is asked there to specify whether the « arrays » use 1bit, 8bits, 32bits, or 64bits (or « unknown ») per (potential) prime.
>> https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/CONTRIBUTING.md#flag-storage <https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/CONTRIBUTING.md#flag-storage>
> 
> ha, i've seen that one a few weeks ago (after some yt video) and to be honnest it's one of these useless speed comparisons (can be fun, but useless as one compares languages with different objectives and doing some prime stuff is hardly representative for usage)


It seems the C++ solutions listed as fastest do quite a part of the job at compile time not at execution time...

The chosen topic (basic sieve and possibly some refinements like « wheel » algorithms) seems to test the capacity of the language to access successive memory addresses in the most efficient way and/or perhaps to move bit patterns around.

Also, it stops at having the array done, but does not address how you use this after the fact.

If the final aim is to print out primes to a file the bottleneck may be rather into the conversion of the bit pattern into explicit ascii bytes... 

For example, if I produce using lualatex a pdf file of all primes less than 999,999,999, most of the time by far is consumed by the typesetting phase (something like 1350 pages, 10 columns per page)

> 
>> I am using luatex for the benchmark because even setting pdftex’s font_mem_size at its maximum TeXLive setting, the memory is at risk of being exhausted on current personal computers  from the condition that the benchmark must iterate at least until a duration of 5 seconds and each iteration re-in allocates a \fontdimen « array » (in the case at hand about 500,000 entries are needed to sieve up to 1,000,000 and memory will get exhausted before the 300th pass)
>> Also it seems luatex runs comparatively faster once the sieving range is large enough (the instantiation step which requires extending dynamically does take some time).
> 
> hm, just allocate the largest fontdimen you need first, that will make the fontdimen array grow at the beginning only (instead of at each step)
> 

This is what I do except for one auxiliary array in the « wheel » because I felt it would be cheating to allocate the 480 slots to start with. I could however have allocated say 1155 = 2310/2 (2310 = 2 * 3 * 5 * 7 *11) slots, wasting some.

But this is executed only once anyhow, at loading time of the « sieve library » independently of the number of passes done during benchmark. Maybe I will do the change for some small gain.

>> I will thus modify the « bit count » tag of my « solution » from unknown to 32bits, thanks to your answer, knowing though that this remains officially unspecified. But the Dockerfile which I was asked to include, and which their benchmarking uses, pulls a texlive-minimal based image dating back to 2018.
>> Perhaps someone here will be interested into contributing a genuine luatex (i.e. using Lua) solution (my code uses only Knuth TeX; there is also a LaTeX3 code also on the github site).
> 
> a lua solution in luatex is just a lua solution -)
> 
>> There is already at least one Lua contribution. I don’t know if a genuine luatex would have to be categorized under « PrimeTeX » or « PrimeLua » ...
>> ... in particular a LuaTeX genuine solution may have a way to use an « array » not based on font dimension parameters.
> 
> mixing lua and tex will also introduce lua call overhead so there is no gain there (maybe let lua do the sqrt but then you can well do all in lua)
> 
> my guess is that the sqrt is the bottleneck
> 
> fontdimens are actually bnto that slow not that slow because they are (1) global so no save stack overhead, and (2) directly accessible because they are part of the font structure (so no tex dimen access overhead)
> 
> also, using etex \dimexpr is also slower than the simple operators

Not to mention that etex division rounds which sometimes is more inconvenient than truncating

On the other hand having \numexpr at once disposal allows to more easily have some namespacing of auxiliary counters, using macros instead of \count's

> 
>> One particular point I don’t know is whether LuaTeX would allow a « faithful » solution: this seems to mean roughly a class-encapsulated one (it is hard to understand what they precisely mean in their guidelines), which I could not really emulate in my code due to global nature of fontdimen assignments.
> 
> hm, do you really need local?

honestly I don’t know exactly what they are aiming at, but I guess basically some piece of code you can re-use in arbitrary code as a library. Global is perhaps not that bad, but having no way to release the memory disqualifies it for faithfulness I believe. The memory can be marked for re-use, but one can not extend the array size after the fact.

anyway, at least some namespace should be added to my solution, I did it (weirdly) for some aspects but not all


> 
> if you use csnames, then you can also consider using \chardef's for numbers (these obey grouping)

ok, the extended range of \char in luatex would indeed help if one needed to store numbers up to the sieving range of 1,000,000. I have some alternative algorithm needing this kind of storage, but a priori when I mentioned csnames it was only to code a « on/off » situation (testing if some number has been marked for composite or no via an \ifcsname, using e-TeX for convenience). Unfortunately this has the overhead of requiring to convert a number into explicit digit tokens.

or is there a way in luatex to tag objects by numbers not having been converted to digit tokens?


> 
>> (I also experimented with  a csname based approach but never could reach comparable speed to fontdimen arrays ; and this required extending other parts of the memory)
> 
> in luatex csname is costly because of the serialization (pdftex is probably faster because there is no utf related overhead)

I did not compare the two. For the fontdimen based approach, at first pdftex looks faster but on closer look for ranges higher than 1,000,000, it seems luatex gets relatively faster, regarding the process of sieving itself.

For example I get this typically on my (slow) machine for sieving up to 100,000,000:

pdftex

Instantiate object for sieving up to 100000000...
...done (0.2322s)
Sieving...
...done (29.4603s)
Outputting to file listofprimes-100000000.txt...
5761455 primes were written to file listofprimes-100000000.txt
...done (22.96228s)
 ) )
No pages of output.
Transcript written on wheel_primestofile.log.

real	0m52.898s
user	0m52.502s
sys	0m0.281s

luatex
Instantiate object for sieving up to 100000000...
...done (3.84619s)
Sieving...
...done (26.5682s)
Outputting to file listofprimes-100000000.txt...
5761455 primes were written to file listofprimes-100000000.txt
...done (28.48254s)
))
warning  (pdf backend): no pages of output.
Transcript written on wheel_primestofile.log.

real	0m59.444s
user	0m58.895s
sys	0m0.445s


The sieving itself seems being done faster by luatex. For some reason the « write to file » part appears slower. As  the « write to a file » was not part of benchmark, I simply issue one \write per prime and it is quite possible gathering together the \write’s by batches could improve.  Not tested.

Something I don’t understand is that the spread between the « base » algorithm (basically the elementary school one, but using only odd numbers from the start, and maybe starting at factor*factor and going by steps of 2*factor) and the « wheel » algorithm (with some primes already sieved out) seems to be greater with pdftex than with luatex: perhaps 2.8 or 2.9 speed gain for pdftex, but only like 2.3 or at most 2.5 with luatex.

> 
>> Here is a link to how the various implementations sort out currently on one specific machine:
>> https://plummerssoftwarellc.github.io/PrimeView/?sc=dt&sd=True&rc=30 <https://plummerssoftwarellc.github.io/PrimeView/?sc=dt&sd=True&rc=30>
> the lua solution they post is not only somewhat slow but also makes some (imo wrong, but who am i to claim) assumptions about how lua stores data so it was not that hard to make a variant that was over 200 times faster

ah very interesting. I was also very surprised that the Lua solution appeared so slow relatively.

Notice by the way that the first Python solution is also very slow... slower than my tex one! (to be fair, slower than my « wheel » one, but Python uses the « base » algorithm)

> 
> because i have a relative old laptop i can't compare with the numbers for e.g. c there (of course lua will be slower)

I think the machine they use for the « PrimeView » is also relatively old (2013). Mine is 2012 and is faster than theirs.

> but as i consider these shootouts useles anyway, i didn't want to spend more time on it (all that docker stuff and such)

I confirm I have spent between 5x and 10x more time with these contributing requirements than with the TeX coding itself. In the end the Dockerfile is very simple but it went through more complicated intermediate versions. I did not want to pull a 4G or 5G texlive image though and initially I was using pdftex but needed to understand how to let it acquire more memory, then I used luatex but I needed to add \pdfresettimer, which finally I did via the \directlua in the tex file itself.

> nor comment on the posted lua code (i never comment on code anyway, unless I know someone well and we can discuss specific issues out of mutual interest)

This is wise indeed.

I know some under-optimal aspects of my contribution and I have not tested some aspects like whether at some location I should use \ifdim rather than \ifnum, or even some other way of testing. I also hesitated regarding the wheel algorithm between using only one giant array, or 480 smaller ones indexed on class modulo 2310, the latter approach reducing the memory impact (by a factor of 1155/480).

Also let me point out that during the various squashes before my PR was merged, I accidentally lost crediting the fact that the \Replicate I use, copied over from xint with removal of e-TeX, was originally basically cloned from the LaTeX3 and has a decades old history I trust.

I have also not tried to optimise how this \Replicate should be used, deciding to nest it with an inner one replicating 1000 times, but never testing if that was actually good.  As the benchmarking overthere is done only for 1,000,000 range, there is danger also to make code seemingly general but in fact tailored for that range only, which would not be entirely fair, imho.


> 
> (messing with bits and storing efficiently in lua probably costs more than it saves, and the same might be true in tex)


Sadly, the nice coincidence that TeX dimensions allow 30 bits and that 30=2*3*5 does not help much as I know no native TeX way to do bitwise operations. We only need two: setting a bit and querying it. This can de done with existing TeX arithmetic and/or macros but will be costly. I did not even try it out.

I also know of no way to initialize a \fontdimen array of a specific size with a specific pattern such as  some non-zero dimension repeated all the way, apart naturally to go through assigning all of them one by one, where the fact that always the same value is used brings no gain whatsoever.

Jean-François

> 
> Hans
> 
> -----------------------------------------------------------------
>                                          Hans Hagen | PRAGMA ADE
>              Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
>       tel: 038 477 53 69 | www.pragma-ade.nl | www.pragma-pod.nl
> -----------------------------------------------------------------