This is the mail archive of the
mailing list for the GCC project.
Re: [FORTRAN PATCH] Reduce gfc_match_strings usage (part 1)
- From: Jerry DeLisle <jvdelisle at verizon dot net>
- To: Roger Sayle <roger at eyesopen dot com>
- Cc: fortran at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Sat, 10 Mar 2007 22:23:05 -0800
- Subject: Re: [FORTRAN PATCH] Reduce gfc_match_strings usage (part 1)
- References: <firstname.lastname@example.org>
Roger Sayle wrote:
I was recently investigating the feasability of adding support for ".xor."
as a synonym of ".neqv." as a GNU extension to the gfortran front-end [to
match the equivalent functionality provided by several commercial fortran
compilers], when I stumbled across match.c:gfc_match_strings.
In the world computer science and compiler design, lexical analysis and
keyword recognition has evolved to a fine-art. Modern techniques using
finite state machines or perfect hash functions now achieve remarkable
efficiency, as per-character processing is often a performance bottle-next
in non-optimizing compilation. The GNU project even has a flex and gperf
tools to simplify the process. gfortran's current gfc_match_strings
implementation possesses none of these virtuous qualities. :-)
Perhaps my bioinformatics/chemoinformatics pattern matching background has
made me sensitive to such inefficiencies , but the proposed patch below
and the following follow-up, provide far more efficient implementations,
based upon the theory/analysis described in .
This first installment proposes as alternative implementation for
primary.c's match_logical_constant to avoid use of gfc_match_strings and
thereby avoids run times that have order dependent upon the number of
pattern strings being matched. This "simple example" should help
introduce the reviewers to the more complex example presented in the
The following patch has been tested on x86_64-unknown-linux-gnu, with a
full "make bootstrap", including gfortran, and tested with a top-level
"make -k check" with no new regressions.
I have a background in logic design and am very familiar with finite state
machines. I also developed a hashed dictionary lookup for language keywords
that was very fast. I am wondering if you have some performance benchmarks with
and without your patches for comparison. It may be illuminating.
Part 1 looks OK to me. I have not looked at Part 2 yet.