6

For some preprocessing task, I would like to use an expl3 property list. Since the number of items in that list would be in the thousands - index entries for a textbook - I was wondering how time-efficient this might be. So, I did some testing:

\documentclass{article}

\usepackage{expl3,xparse, fp}

% timing adapted from http://tex.stackexchange.com/questions/9087
\def\startTimer{\pdfresettimer}
\def\stopTimer{%
    \FPdiv\result{\the\pdfelapsedtime}{65536}
    \FPround\result{\result}{3}\par 
    Time (seconds): \result \par}

\ExplSyntaxOn

\prop_new:N \sg_user_mapping
\cs_generate_variant:Nn \prop_gput:Nnn { Nxx }

\int_new:N  \i_target
\int_new:N  \i_counter

\NewDocumentCommand{\dostuff}{m} {
    Adding\ #1\ keys\ to\ user\ mapping\par
    %\prop_gclear:N \sg_user_mapping
    \startTimer
    \int_add:Nn \i_target {#1}
    \int_zero:N \i_counter % Hopefully obvious!

    \int_while_do:nn { \i_counter < \i_target }
    {
        \edef\wurst{\int_to_arabic:n \i_counter}
        \prop_gput:Nxx \sg_user_mapping {hans\wurst} {0}
        \int_incr:N \i_counter
    }
    \stopTimer\par
}

\ExplSyntaxOff

\begin{document}

\ttfamily

\dostuff{10} 
\bigskip

\dostuff{100} 
\bigskip

\dostuff{1000} 
\bigskip

\dostuff{10000} 

\end{document}

Here is what I get:

enter image description here

So, that is a clear case of O^2; I'm guessing that the entire list gets scanned before a new entry is inserted.

I'm wondering if it would be viable to use some behind-the-scenes trickery in order to exploit pdftex's built-in hashtables. For example, for each key-value pair,

  1. sanitize the key by stripping out any characters that can't be part of a command name: #foo%^bar!- baz? becomes foobarbaz

  2. create a property list (as currently implemented) under the name \pl_userland_foobarbaz

  3. store #foo%^bar!- baz? => whatever value in that list.

I actually tried that, and the code, while obviously slower for small numbers of keys, does scale with O^1 as expected, and it reaches parity with the straight, simple property list at about 1000 keys. I hesitate to post that code here, since I'm only beginning with expl3, and the pros could probably do a better job of it; it was only an experiment.

Of course my suggestion brings up the question how many such keys and property list instances pdfTeX will be able to accommodate before starting to throw the toys out of the pram? Alternatively, it may be possible to implement a proper hash table in TeX itself; but I'm not up to snuff in that regard.

  • 2
    The TeX-sx model works poorly for discussion (quite deliberately: there's no threading, for example). The 'official' place for such things in a LaTeX3 context is LaTeX-L: listserv.uni-heidelberg.de/cgi-bin/wa?A0=LATEX-L – Joseph Wright Dec 4 '16 at 21:22
  • 2
    Not related to the question, but note that expl3 has an FPU, so you don't also need fp here, you can use \fp_eval:n. – Joseph Wright Dec 4 '16 at 21:23
7

First off, it's important to emphasis that only the interfaces are documented for expl3 and that the implementation may change with no notice provided the interfaces are unchanged. (Over my time on the team we've had a couple of different implementations here, and there was at least one more in the past.) The current implementation uses a single macro to hold the entire property list (the previous one uses a single toks, and before that there was some csname oddness: before my time!).

As discussed in detail in How to implement (low-level) arrays in TeX, the most efficient way to implement an array for fast lookup in TeX is to use the hash table and make sure your control sequence names don't cause too many clashes. (Basically, don't use numbers!)

However, this was not the key design driver in the design of the current prop data type in expl3. The code has developed since before the release of LaTeX2e (1994) and there certainly was another worry: memory. Today there are many more csnames available in a standard TeX binary, so the pressure to preserve them is reduced (though it is still possible to run out, depending on the use case). Twenty years ago the pressure was much more severe: famously, there were then only about 50 'spare' names after loading the LaTeX2e kernel when using TeX on MS-DOS. That factor is one of those here: the implementation has altered over time, but not simply burning through names remains one factor.

There are also other considerations. Whilst random lookup is fast using a hash table approach, copying a property list is easier when 'behind the scenes': it's a one-shot not a loop. There's also the question of mapping over each entry in a list: for the current set up, we can expand the underlying macro and then work through the entries on the stack. Using separate macros for each entry makes that process more tricky.

The team have discussed using different implementations, but to date there's been no strong push to do so from the point of view of 'use cases' (certainly for the team's own code). Balancing up the various use cases is non-trivial, and we have discussed an 'object' type which would have a more than one 'back end' and would switch between them (perhaps via a user setting).

  • Thanks, great discussion of the various aspects involved. As long as the current implementation remains, it might be worthwhile to mention the O^2 scaling in the docs. Maybe what really needs to be done is a modification to pdfTeX itself, so as to make the hash table creation function available to TeX code. (Which of course raises the question of memory management; yet, I think with just a bit more help from the engine wrt composite data structures and communication to the outside world, TeX programming could actually be fun. And yes, there is luaTeX, but it adds too much and is slow.) – Michael Palmer Dec 4 '16 at 21:49
  • @MichaelPalmer I'm not sure what you mean about the hash table! On LuaTeX, it's not that slow considering it's Unicode (the comparison normally made is that when TeX was written it took minutes for each page of simple text: of course people nowadays have different expectations). On documenting the behaviour, I'm wary: that would basically lock in a particular implementation. – Joseph Wright Dec 5 '16 at 18:06
  • @JosefWright - pdfTeX deals with unicode too, no? My uninformed guess is that inserting hooks into all stages of document processing slows LuaTeX down. About the hashtable: it would be nice if one could just create additional hashtable instances in userland - just like Lua permits. The pdfTeX engine obviously creates hashtables internally, but it does not allow one to instantiate additional ones. – Michael Palmer Dec 5 '16 at 18:14
  • 1
    @MichaelPalmer pdfTeX is an 8-bit program, so the internal data structures are all of fixed 1-byte-based size. In contrast, LuaTeX is natively Unicode, and for most 'real world' uses will be loading OpenType fonts needing a shaper not .tfm files (so for actual typesetting more work is needed). LuaTeX also exposes internals which means more code ... But all of that is a different question! – Joseph Wright Dec 5 '16 at 18:17
  • @JosefWright - if I run the exact same document of ~400 typeset pages - and with a dubious home-brewed page breaking algorithm, which slows things down - and using the same Type I fonts (Lucida Bright) through pdfTeX, it takes 8 seconds. With LuaTeX, it takes 28 seconds. I just can't imagine that unicode causes that much of a difference. But as you say, it's a different question. Thank you again for all your explanations, and for the work you and others put into the most excellent expl3 package. – Michael Palmer Dec 5 '16 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.