Mail #6119

Back to main page of archive

Previous mail   Next mail   Unformatted/full headers
Overview  10 days   Subject   Date   Thread   Author  

From: Mirsad Todorovac
Subject: Sppeding up GPC :-) ...
Date: 11 Jan 2002, 19:31:02

Hi, all - have a nice weekend first,

Since this is not a bug report, relax all!

I was puzzled by 'Highlights' section of GPC manual that says how GNU
Pascal compiler is substantially slower. I know of course that it uses
proven GNU backend, so GPC team has little influence in making *that* part
run faster.

I know that reliability is more important than speed, but a question
occured to me. While I was still at the college, we had an collegium
called "Language Processors". It had subjects like LL-grammar, attribute
grammar etc., which are mathematical background for compilers.

On labs, we had a choice, whether to use code parser, or a 'finite stata
automata' (FSA) driven parser. I chose the latter which made me a lot of
complications; but impression of all students was that FSA parser is
substantially faster.

Why is this - FSA parser is very small piece of code driven by a table
that represents it's wisdom and logic, which serves to approve or reject
syntax.

I realized GPC is using 'bison' parser as it's front end - and 'bison'
(yacc successor) AFAIK uses code-driven parsing generated from attribute
LALR(1) grammar, doesn't it?

What is your estimate, is there a chance of leap increase of speed if
switching bison to use FSA-syntax checker? So he would generate part of
compiler that does the same grammar, but by different method, finite state
automata (FSA). FSA parsers are known to be more compact, but harder to
design.

Modern machine architectures would make FSA parser run even faster, since
(realtively small) table and driver code can fit into most processor's
caches nowadays, making compilation fly.

Besides that, grammar can be spearated from generated code, so (in some
ideal case) there would be no need to recompile driver part of the
compiler, only compiler table - when changing or debugging grammar.

My estimation that this change could help reduce compile time by 50% to
70%; and decrease compiler binary size (parser part) by 30-60%, switching
syntax (by compiler directive) would then be a switch of table, while
automate driving code would remain the same.

This change doesn't influence RTL generator and back-end, neither lexer
front-end (but there's a room for finite-state automata strategy
improvements there also).

Of course, although this improvement would carry an opportunity to catch
up with Borland Pascal in speed, but GNU backend's generality makes this
very hard as I suspect.

Now, these are only reflections, I haven't sunk that deep in 'bison' nor
GPC internals - but please tell me that this line of research have a
sense or not.

Of course, counter-argument is always 'why touch something stable, when
there's more important work to do, like catching up with standards?' - but
tuning performance of code was always my weakness from college days ;-)

Once again, have a nice weekend,
Mirsad

--
This message has been made up using recycled ideas and language constructs.
No plant or animal has been injured in process of making this message.

Previous mail   Next mail   Unformatted/full headers
Overview  10 days   Subject   Date   Thread   Author  

Replies

Back to main page of archive

Note: This page contains information that does not originate from the owner of this web site, but from the authors of the mails archived. The owner of this web site is not responsible for the content of such information. Any use of that infomation requires the consent of the respective author.

Where WWW addresses (URLs) in the mails archived are marked as hyperlinks, this is only for the comfort of the reader. The content of the web pages linked to like this does not necessarily reflect the opinion of the owner of this web site or of the authors of the mails archived. The owner of this web site is not responsible for the content of such web pages. Those pages are explicitly not to be considered as part of the content of this page, but merely as references.

This page was created by Crystal 0.999 (Linux 2.4.27/i686).