[PATCH 0/3] yacc: compute the best type for the state number

[Akim Demaille]

Hi Tom,

This should address your concern.

Hi Paul,

I need your expertise here, if you have some time.

Currently we use the "best" integral type for tables, including those
storing state numbers.  However the variables used in yyparse (and its
dependencies such as yy_stack_print) use a mixture of int and int16_t
invariably.  As a consequence, very large models overflow these
variables, and that's Tom's report
(https://lists.gnu.org/archive/html/bug-bison/2019-09/msg00018.html).

As a matter of fact, we used two types:

- most arrays (such as state stack, and its correspondance in the LAC
  infrastructure) are using int16_t.  A few "temporary" variables also
  have this type.

- yystate, which is an intermediate variable, was an int.

In my proposal below, I fuse both cases to use a single type,
yy_state_num, which is the smallest type that contains the set of
states: an unsigned type.

That's where I need you Paul: do you think that, for sake of
performances, I should keep the scalar variable as an 'int', and move
to the unsigned type only for arrays?  Is it ok to move to stacks of
uint8_t instead of uint16_t, or should we stick to larger types?  I
can see how using small types is cache friendly, but I can also
imagine that cpus don't like small types.



This is currently in the 'fix-state-type' branch, which, amusingly, is
about not having a fix type for states.  It's also available here:

https://www.lrde.epita.fr/~akim/private/bison/bison-3.4.2.117-7e3dc.tar.gz
https://www.lrde.epita.fr/~akim/private/bison/bison-3.4.2.117-7e3dc.tar.xz

Cheers!


Akim Demaille (3):
  style: change misleading macro argument name
  yacc: introduce a type for states
  yacc: use the most appropriate integral type for state numbers

 data/skeletons/glr.c  |  4 +-
 data/skeletons/yacc.c | 71 +++++++++++++++++---------------
 tests/linear          | 94 +++++++++++++++++++++++++++++++++++++++++++
 tests/local.mk        |  2 +-
 tests/torture.at      | 43 +++++++++++++++++---
 5 files changed, 172 insertions(+), 42 deletions(-)
 create mode 100755 tests/linear

-- 
2.23.0