On 8/3/2021 3:26 PM, jfbu wrote:
Le 3 août 2021 à 12:49, Hans Hagen <[email protected]> a écrit :
On 8/3/2021 9:45 AM, jfbu wrote:
Hi,
Le 3 août 2021 à 09:09, Hans Hagen <[email protected]
<mailto:[email protected]>> 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...
that's why comparing script languages and compiled ones makes no sense
(one can argue for jit but in e.g. luatex that doesn't pay of)
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.
but that is not made clear -)
Also, it stops at having the array done, but does not address how you use this
after the fact.
indeed
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...
then lua might perform better because it's all about strings (although
printing numbers is a bad example as they all differ here)
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)
sure because quite some processing kicks in there (fonts, backend,
columnization) but also the way that big array gets serialized
but 1350 pages for 999.999.999 is not that bad because here 10.000.000
in 12 columns and an 8pt monospaced font takes 955 pages and indeed some
runtime (using context that is, latex is supposed to be faster)
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.
even in lua you'd waste them and if oen goes hash there is more overhead
(linked list) than in an array
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
(it's why in luametatex we have : for integer division, but that's
another story)
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
hm. a bit expansive, \chardefs etc are cheaper
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.
font memory is never released anyway
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.
there is of course a limit in the size of the hash table that you can hit
or is there a way in luatex to tag objects by numbers not having been converted
to digit tokens?
not in luatex
(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.
hm, maybe hash misses kick in which means a chain lokup (maybe be faster
in luatex than in pdftex)
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.
could be because there is some utf juggling but it shoul dnot make a
huge dent
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.
hard to say ... maybe cpu cache (different programs, different code)
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.
the latets version posted there is already better but i'll mail you an
variant of that that is about three times faster
- basic performance : 1.90
- make functions local : 1.84
- inline the two functions : 1.52
- use integer division : 1.27
- some more : 0.71
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)
object oriented pverhead i guess (the few times that i ran into some
python code it was easy to make faster lua variants)
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).
it looked at the code but it will take me too much time to check where
it can be made faster (saw a few spots) as i have to make sieve only
macro then
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.
dunno, loops can be very fast when done right (and when on eknows where
tex's bottlenecks are -)
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.
maybe don't pass the number but put it in a register ; this romannumeral
is also kind of strange (not sure why you need it ; actually you should
time romannumeral in pdftex vs luatex .. could be more efficient in
thelater
(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.
this is off topic but in luametatex we can do
\scratchcounter 1
\scratchcounter \numexpression \scratchcounter bor 4\relax
\the\scratchcounter : 5
which performs quite ok (1 milion times takes .27 sec on my machine)
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.
ok, but when you pack bits you do 32 per stel so you migth end up in the
'seconds' range
i'll mail you my test file
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
-----------------------------------------------------------------
