# Does writing to a property list take longer than writing to a token list?

In the question Write a column selectively to the appropriate row using pgfplotstable? I offered the following:

\documentclass{article}

\usepackage{xparse}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{filecontents}

\begin{filecontents*}{namespgfa.csv}
5501,Kathirvelu A
5502,Gugan K
5503,Kalaitchelvi S
5504,Suresh S
5505,Mahesh K
\end{filecontents*}
%
\begin{filecontents*}{markspgfa.csv}
5501,67
5502,25
5503,62
5505,95
\end{filecontents*}

\ExplSyntaxOn
\tl_new:N \g_tab_rows_tl
\ior_new:N \g_names_ior
\ior_new:N \g_marks_ior
\prop_new:N \g_names_prop

\ior_open:Nn \g_names_ior {namespgfa.csv}
\ior_open:Nn \g_marks_ior {markspgfa.csv}

\cs_new:Npn \set_name_keys:w #1,#2\q_stop
{
\prop_put:Nnn \g_names_prop {#1} {#2}
}

\cs_new:Npn \tab_write_keys:w #1,#2\q_stop
{
\prop_gpop:NnN \g_names_prop {#1} \l_tmpa_tl
\tl_gput_right:Nn \g_tab_rows_tl {#1&}
\tl_gput_right:NV \g_tab_rows_tl \l_tmpa_tl
\tl_gput_right:Nn \g_tab_rows_tl {&#2\\}
}
%replacing the above two control sequences with the following slows compilation substantially
%\cs_new:Npn \set_name_keys:w #1,#2\q_stop
%   {
%        \prop_put:Nnn \g_names_prop {#1} {#1&#2&}
%   }
%
%\cs_new:Npn \tab_write_keys:w #1,#2\q_stop
%    {
%        \prop_gpop:NnN \g_names_prop {#1} \l_tmpa_tl
%        \tl_gput_right:NV \g_tab_rows_tl \l_tmpa_tl
%        \tl_gput_right:Nn \g_tab_rows_tl {#2\\}
%    }

\ior_str_map_inline:Nn \g_names_ior
{
\set_name_keys:w #1\q_stop
}

\ior_str_map_inline:Nn \g_marks_ior
{
\tab_write_keys:w #1\q_stop
}

\ior_close:N \g_names_ior
\ior_close:N \g_marks_ior

\NewDocumentCommand { \WriteRows } {}
{
\tl_use:N \g_tab_rows_tl
}

\ExplSyntaxOff

\begin{document}

\begin{longtable}{clc}
Reg.No.&Name&Marks\\
\toprule
\WriteRows
\bottomrule
\end{longtable}

\end{document}


Background: The first column of both namespgfa.csv and markspgfa.csv contains id numbers, while the second column contains a corresponding name and mark respectively. The idea was very basic: associate each id with a name, and insert that name between the corresponding id and mark in a table. Since speed was an issue, I thought that the commented changes in the above code might speed things up. My thinking was that on for .csv with n lines, \set_name_keys:w will get called n times regardless, therefore using that cs to write some extra information would save ~n calls to \tl_gput_right:Nn \g_tab_rows_tl {#1&}. However, on test .csv's with 4000 lines, the second method took ~30s while the first took ~25.

My question is: why is there such a substantial difference in compile times?

Here are the test files I used:

To use these, remove the "a" from the filenames in \ior_open:Nn \g_names_ior {namespgfa.csv} and \ior_open:Nn \g_marks_ior {markspgfa.csv}.

-
Thanks @lockstep, didn't know of the profiling tag, perhaps someone could suggest an efficiency synonym...that one's a little hard to find unless you know what to look for :) –  Scott H. Jul 28 '12 at 19:02
I'm a bit confused on the times there: as currently written it says '30 s' and '25 s', which is not a substantial difference. The linked files are also pretty small: only a few lines, but the question says '4000 lines'. –  Joseph Wright Jul 28 '12 at 20:14
@JosephWright While not a major difference in absolute time, the 20% increase was something I couldn't understand as my (obviously naive) thought was that it would decrease the compilation time. I checked the files and they are the correct size. Could you have compiled without removing the filecontents (which was left there to make the example working) in which case the downloaded files may have been overwritten? I'll edit the code so that won't happen. –  Scott H. Jul 28 '12 at 20:54

## 1 Answer

Ultimately, expl3's prop data type is constructed using a TeX macro (at the moment: we used to use token registers). When you assign to a prop, the assignment first needs to 'look' for the key before either adding a new key/value pair or replacing the value for an existing key. This is done using a delimited macro at the TeX level. So when you add to a prop, TeX has to read over all of the tokens in the underlying macro, which gets slower as the content gets larger. On the other hand, assigning to a tl (which is also a macro at the TeX level) does not involve a parsing step, so the only size consideration is what you are adding, not what is already there. Thus ultimately anything which makes prop variables larger will slow things down. It's of course a balance (as each assignment takes time), but if you are looking at very large structures and large numbers of tokens then splitting things up may be more efficient.

(There is an experimental 'data table' data type in the team SVN. This shows the same problem, but to a greater extent, and I am intending to revise the code to use more csnames each containing less data, as the balance here is clearly wrong.)

-
Thanks Joseph, that makes perfect sense. –  Scott H. Jul 28 '12 at 21:39
As a follow up, in a simple write/retrieve situation like this (where duplicate "keys" don't exist and don't get changed) writing pairs sequentially to a token list/sequence and then parsing afterwards to recover items would eliminate the parse on write aspect and, depending on implementation, possibly be more efficient? Are there any specific gains associated with retrieval from a property list as opposed to a sequence/token list? –  Scott H. Jul 28 '12 at 21:51
Sorry Joseph, but this answer is partially wrong: \tl_put_right:Nn also takes a time proportional to the number of tokens in the final token list. The reason prop operations are slower is that we go twice through all tokens: once to see if the key is new or not, and once to add the new key-value and do the assignment. We could do some crazy optimizations of prop operations to only have one pass, but I'm not sure yet whether this is needed. –  Bruno Le Floch Jul 28 '12 at 21:52
@ScottH. Props (called dictionaries in other programming languages) are currently the best way to handle the kind of data you have. Joseph has written an experimental module for data tables, but both implementation will take a time quadratic in the number of lines (adding each line takes a time proportional to the number of lines already added). Adding the data one line at a time to a token list won't help, it is still quadratic. I'd like to change l3dt to use a linear approach, where the whole file is read, and the data is stored at once. But retrieval remains tricky and quadratic. –  Bruno Le Floch Jul 28 '12 at 21:59
@BrunoLeFloch could you expand on your first comment a little. I've left the question open to give you a chance to answer. I'm confused about (1) why a second pass is required or (2) why increasing the length of values causes the scan for duplicate keys to take that much longer. I'm guessing that the compiler needs to check every token to see whether it is the start of a key delimiter, including tokens contained in values? –  Scott H. Jul 28 '12 at 23:45