Declaring acronyms in v3.7+ takes far longer to process than in v2

[ytzemih]

Hi, after reinstalling my Linux, I'm now using

pdfTeX, Version 3.141592653-2.6-1.40.24 (TeX Live 2022/Debian)

with acro 3.8. I'm actually mostly using lualatex. I'm using the acro package settings

\acsetup{language = english,list/template = longtable,cite/group = true}

together with around 200 acronyms in a mid-size LaTeX beamer document.

For some reason, the change to my new Linux installation (with an updated acro) now leads to very long compilation times. Both TeX engines halt for about 4-5 minutes at

(/usr/share/texlive/texmf-dist/tex/latex/acro/acro.sty
(/usr/share/texlive/texmf-dist/tex/latex/translations/translations.sty))

only for then to continue as usual. The resulting document looks fine, acro itself is not complaining and no other errors or warnings related to my use of acro appear.

I've introduced language=english above in the hope that the override of auto solves the problem but that didn't work.

Before the Linux re-installation, translations.sty took quite long as well (maybe 15-20 secs), but it was still bearable. Is this a known issue and/or is there anything that I can do? Thank you for any further hints.

[dbosk]

It's not translations.sty that takes long. It's something else. You can probably see that the parenthesis is closed after translations.sty) when it slows down. So it's something after that.

I have experienced exactly the same, but with other outputs.

(/usr/local/texlive/2024/texmf-dist/tex/latex/acro/acro.sty
(/usr/local/texlive/2024/texmf-dist/tex/latex/l3packages/l3keys2e/l3keys2e.sty)
) (/home/dbosk/texmf/tex/latex/acrox/acro.style.adx.code.tex)
(/home/dbosk/texmf/tex/latex/acrox/acro.style.possessive.code.tex)
(/usr/local/texlive/2024/texmf-dist/tex/latex/base/textcomp.sty)

Here it halts for a minute or two before it resumes execution. After that we see it continues with the next thing (preamble-thesis.tex).

(/usr/local/texlive/2024/texmf-dist/tex/latex/acro/acro.sty
(/usr/local/texlive/2024/texmf-dist/tex/latex/l3packages/l3keys2e/l3keys2e.sty)
) (/home/dbosk/texmf/tex/latex/acrox/acro.style.adx.code.tex)
(/home/dbosk/texmf/tex/latex/acrox/acro.style.possessive.code.tex)
(/usr/local/texlive/2024/texmf-dist/tex/latex/base/textcomp.sty)))                 
(./preamble-thesis.tex)

But judging from the parentheses (it closes two parentheses )) after slowing down), it's not in the acro package, but after. That's where my acro declarations are.

This part from the detailed log:

(/usr/local/texlive/2024/texmf-dist/tex/latex/acro/acro.sty
(/usr/local/texlive/2024/texmf-dist/tex/latex/l3packages/l3keys2e/l3keys2e.sty
Package: l3keys2e 2024-03-14 LaTeX2e option processing using LaTeX3 keys
)
Package: acro 2022/04/01 v3.8 typeset acronyms and other abbreviations (CN)

\l__acro_tmpa_int=\count532
\l__acro_tmpb_int=\count533
\l__acro_tmpc_int=\count534
\l__acro_tmpd_int=\count535
Loading module `base' ...
Loading module `interface' ...
Loading module `aux' ...
Loading module `properties' ...
Loading module `acronyms' ...
Loading module `formatting' ...
Loading module `ppfixes' ...
Loading module `tools' ...
\l__acro_minimal_usage_int=\count536
\l__acro_nest_int=\count537
\g_acro_barrier_int=\count538
\g_acro_barrier_total_int=\count539
Loading module `commands' ...
\l_acro_nest_level_int=\count540
Loading module `templates' ...
Loading module `list' ...
Loading module `pages' ...
\l__acro_pages_seq_threshold_int=\count541
Loading module `locale' ...
Loading module `pdfsupport' ...
Loading module `patch' ...
Loading module `definitions' ...
Loading module `upgrade' ...
)

Package acro Info: Loading module `style.adx' ...

 (/home/dbosk/texmf/tex/latex/acrox/acro.style.adx.code.tex
File: acro.style.adx.code.tex 2022/04/01 v3.8 acro style file `style.adx' ()
)

Package acro Info: Loading module `style.possessive' ...


(/home/dbosk/texmf/tex/latex/acrox/acro.style.possessive.code.tex
File: acro.style.possessive.code.tex 2022/04/01 v3.8 acro style file `style.pos
sessive' ()
)
(/usr/local/texlive/2024/texmf-dist/tex/latex/base/textcomp.sty
Package: textcomp 2020/02/02 v2.0n Standard LaTeX package
)
\ProtoArrowLength=\skip292
\c@g@acro@PPT@int=\count542
\c@g@acro@PPTM@int=\count543
\c@g@acro@IND-CPA@int=\count544
\c@g@acro@IND-CCA@int=\count545
\c@g@acro@IND-SFCCA@int=\count546
\c@g@acro@WUF-CMA@int=\count547
\c@g@acro@SUF-CMA@int=\count548
\c@g@acro@INT-PTXT@int=\count549
\c@g@acro@INT-SFPTXT@int=\count550
\c@g@acro@INT-CTXT@int=\count551
\c@g@acro@INT-SFCTXT@int=\count552
\c@g@acro@DEN-SS@int=\count553
\c@g@acro@DLP@int=\count554
\c@g@acro@DH@int=\count555
\c@g@acro@DHA@int=\count556
\c@g@acro@DHP@int=\count557
\c@g@acro@DDH@int=\count558
\c@g@acro@DC@int=\count559
\c@g@acro@DCP@int=\count560
\c@g@acro@SMP@int=\count561
\c@g@acro@LWE@int=\count562
\c@g@acro@OTP@int=\count563
\c@g@acro@AES@int=\count564
\c@g@acro@ZK@int=\count565
\c@g@acro@ZKP@int=\count566
\c@g@acro@PK@int=\count567
\c@g@acro@ZKPK@int=\count568
\c@g@acro@NIZK@int=\count569
\c@g@acro@MA@int=\count570
\c@g@acro@MAC@int=\count571
\c@g@acro@HMAC@int=\count572
\c@g@acro@PRP@int=\count573
\c@g@acro@PRG@int=\count574
\c@g@acro@PRF@int=\count575
\c@g@acro@VRF@int=\count576
\c@g@acro@PRNG@int=\count577
\c@g@acro@RNG@int=\count578
\c@g@acro@HE@int=\count579
\c@g@acro@KEM@int=\count580
\c@g@acro@DEM@int=\count581
\c@g@acro@EtM@int=\count582
\c@g@acro@PIR@int=\count583
\c@g@acro@OT@int=\count584
\c@g@acro@KE@int=\count585
\c@g@acro@DHKE@int=\count586
\c@g@acro@AKE@int=\count587
\c@g@acro@PFS@int=\count588
\c@g@acro@PKC@int=\count589
\c@g@acro@PKE@int=\count590
\c@g@acro@SKE@int=\count591
\c@g@acro@BE@int=\count592
\c@g@acro@ANOBE@int=\count593
\c@g@acro@oANOBE@int=\count594
\c@g@acro@DBE@int=\count595
\c@g@acro@DeBE@int=\count596
\c@g@acro@KD-HES@int=\count597
\c@g@acro@IBE@int=\count598
\c@g@acro@ABE@int=\count599
\c@g@acro@CP-ABE@int=\count600
\c@g@acro@KP-ABE@int=\count601
\c@g@acro@PE@int=\count602
\c@g@acro@PRE@int=\count603
\c@g@acro@FHE@int=\count604
\c@g@acro@SHE@int=\count605
\c@g@acro@SHA@int=\count606
\c@g@acro@OTR@int=\count607
\c@g@acro@DP@int=\count608
\c@g@acro@Tor@int=\count609
\c@g@acro@Sphinx@int=\count610
\c@g@acro@UC@int=\count611
\c@g@acro@ABC@int=\count612
\c@g@acro@AC@int=\count613
\c@g@acro@IBAC@int=\count614
\c@g@acro@ABAC@int=\count615
\c@g@acro@RBAC@int=\count616
\c@g@acro@DAC@int=\count617
\c@g@acro@acMAC@int=\count618
\c@g@acro@IFC@int=\count619
\c@g@acro@BLP@int=\count620
\c@g@acro@ACL@int=\count621
\c@g@acro@FS@int=\count622
\c@g@acro@eID@int=\count623
\c@g@acro@PKI@int=\count624
\c@g@acro@CA@int=\count625
\c@g@acro@PUF@int=\count626
\c@g@acro@DB@int=\count627
\c@g@acro@DBMF@int=\count628
\c@g@acro@DBDF@int=\count629
\c@g@acro@DBEDLC@int=\count630
\c@g@acro@DBDH@int=\count631
\c@g@acro@DBTF@int=\count632
\c@g@acro@DBIF@int=\count633
\c@g@acro@DBIV@int=\count634
\c@g@acro@DBPK@int=\count635
\c@g@acro@PPK@int=\count636
\c@g@acro@DFKOmodel@int=\count637
\c@g@acro@LBS@int=\count638
\c@g@acro@PROPS@int=\count639
\c@g@acro@LP@int=\count640
\c@g@acro@LPS@int=\count641
\c@g@acro@MPC@int=\count642
\c@g@acro@SMC@int=\count643
\c@g@acro@UN@int=\count644
\c@g@acro@NSA@int=\count645
\c@g@acro@GCHQ@int=\count646
\c@g@acro@CIA@int=\count647
\c@g@acro@TAO@int=\count648
\c@g@acro@FRA@int=\count649
\c@g@acro@ICT@int=\count650
\c@g@acro@PET@int=\count651
\c@g@acro@DoS@int=\count652
\c@g@acro@DDoS@int=\count653
\c@g@acro@APT@int=\count654
\c@g@acro@DRM@int=\count655
\c@g@acro@E2E@int=\count656
\c@g@acro@CSP@int=\count657
\c@g@acro@ISP@int=\count658
\c@g@acro@TPM@int=\count659
\c@g@acro@DAA@int=\count660
\c@g@acro@TTP@int=\count661
\c@g@acro@NFC@int=\count662
\c@g@acro@WWW@int=\count663
\c@g@acro@URL@int=\count664
\c@g@acro@URI@int=\count665
\c@g@acro@URN@int=\count666
\c@g@acro@OSN@int=\count667
\c@g@acro@DOSN@int=\count668
\c@g@acro@SNS@int=\count669
\c@g@acro@IM@int=\count670
\c@g@acro@TOC@int=\count671
\c@g@acro@GPG@int=\count672
\c@g@acro@PGP@int=\count673
\c@g@acro@IO@int=\count674
\c@g@acro@P2P@int=\count675
\c@g@acro@DHT@int=\count676
\c@g@acro@DLT@int=\count677
\c@g@acro@tposet@int=\count678
\c@g@acro@UX@int=\count679
\c@g@acro@GDPR@int=\count680
\c@g@acro@WF@int=\count681
\c@g@acro@WFWO@int=\count682
)
\c@g@acro@OS@int=\count683
\c@g@acro@RPS@int=\count684
\c@g@acro@OR@int=\count685
\c@g@acro@POR@int=\count686
\c@g@acro@SPOR@int=\count687
\c@g@acro@SPORES@int=\count688
\c@g@acro@MITM@int=\count689
)
(./preamble-thesis.tex) 

Maybe it takes time to process many acronyms? I'll try to work out an MWE at some point, but I'm not suffering enough to warrant making it a priority to debug it further.

[ytzemih]

Thanks, @dbosk for testing that. After crafting an MWE with 1 to ca. 400 entries, I can confirm, it's not translations.sty, it's simply the list of acronyms created with \DeclareAcronym. The MWE looks roughly like this (but I used my own acronyms with the majority of acronyms using the standard plural form):

\documentclass{article}
\RequirePackage{acro}[=v2] % <== include/exclude version flag
\DeclareAcronym{Test001}{short = TST001, long = {Test 001}, long-plural-form = {Tests 001}}
\begin{document}
\ac{Test001}
\end{document}

I did some non-comprehensive experiments with pdflatex and lualatex as well as with acro v2 and v3.7/3.8 with the following results:

with acro v3.7/3.8:

• 1-10 entries take <1 sec
• ca. 100 entries take around 10 sec
• ca. 200 entries take around 35 sec
• ca. 300 entries take around 1:54 min
• ca. 400 entries take around 4-5 min

with acro v2:

• ca. 300 entries take <1 sec
• ca. 400 entries take around 1 sec

It is as if v3.7+ introduce features with some intense calculations AND with exponential complexity, while v2 seems not to use such calculations OR its algorithms manage to remain in logarithmic or linear complexity.

After a quick test, I can't seem to recognize any significant difference for the MWE between lualatex and pdflatex.

[dbosk]

Thanks @ytzemih for doing that!

I can add that I used xelatex.

[u-fischer]

Well one problem is that everytime a new entry is added acro goes over the full list to remove duplicates. That is rather unsane. If I disable the removal the compilation from the following document drops from 11.5s to 1.5s. That is still slow (acro seems still to map over all entries in other places), but at least bearable.

\documentclass{book}
\usepackage{l3benchmark}
\usepackage{acro}
\ExplSyntaxOn
\benchmark_tic:
\cs_set_eq:NN\saved_seq_gremove_duplicates:c\seq_gremove_duplicates:c
%\cs_set_eq:NN\seq_gremove_duplicates:c\use_none:n
\int_step_inline:nn{100}{
\DeclareAcronym{ARPANET#1}{
    short = ARPANET#1,
    long = Advanced Research Projects Agency Network
}}
\cs_set_eq:NN\seq_gremove_duplicates:c\saved_seq_gremove_duplicates:c
\benchmark_toc:
\ExplSyntaxOff
\begin{document}
blub
\end{document}

[dbranford]

Looking for \seq_gremove_duplicates:c

acro/code/acro.aux.code.tex

Lines 71 to 80 in 9a56e41

	\cs_new_protected:Npn \__acro_auxlist_add:nn #1#2
	{
	\str_set:Nn \l__acro_tmpa_str {#2}
	\acro_attribute_set:nnn {#1} {#2} {}
	\seq_if_in:cVT {g__acro_auxlist_#1_seq} \l__acro_tmpa_str
	{ \seq_gremove_all:cV {g__acro_auxlist_#1_seq} \l__acro_tmpa_str }
	% \acro_auxlist_write_entry:nn {#1} {{#2}}
	\seq_gput_right:cV {g__acro_auxlist_#1_seq} \l__acro_tmpa_str
	\seq_gremove_duplicates:c {g__acro_auxlist_#1_seq}
	}

seems to be responsible, it's run per-property per-acronym so certainly adds up. It comes from d2479bb which didn't obviously add it to fix anything, and nowhere else duplicates might be introduced to the seqs jumps out to me.

Removing it works fine in a basic instance, does it cause issues in fuller examples?

\cs_set_protected:Npn \__acro_auxlist_add:nn #1#2
  {
    \str_set:Nn \l__acro_tmpa_str {#2}
    \acro_attribute_set:nnn {#1} {#2} {}
    \seq_if_in:cVT {g__acro_auxlist_#1_seq} \l__acro_tmpa_str
      { \seq_gremove_all:cV {g__acro_auxlist_#1_seq} \l__acro_tmpa_str }
    \seq_gput_right:cV {g__acro_auxlist_#1_seq} \l__acro_tmpa_str
  }

[sasozivanovic]

I believe there is another problem: acro constructs very long token lists, e.g. \g_acro_acronyms_seq, which is populated by \DeclareAcronym, and it also appends lots of items to the enddocument hook (by \ac and friends).

According to PGF source, adding to token lists has quadratic runtime. And indeed, my measurements confirm this claim. The first invocation of \DeclareAcronym took 0.00954s, the 100th invocation 0.0413s (without removing duplicates). For \ac: from 0.00104s to 0.00491s.

To fight the quadratic runtime problem (when constructing so-called soft paths), PGF does not add tokens to the list directly, but via two intermediate buffers, see the code in the file linked to above. I believe that a similar approach would immensely speed up acro as well.

[u-fischer]

@sasozivanovic expl3 contains for such large token lists the l3tl-build module, see interface3.pdf.

[sasozivanovic]

@u-fischer Even better, this should make it easier for the author to fix the package, if he decides to do so! Thanks for the pointer.