chicken-hackers
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)


From: felix . winkelmann
Subject: Re: [Chicken-hackers] [PATCH] fix #1648 (correctly)
Date: Sat, 05 Oct 2019 19:47:51 +0200

> >Left as an exercise to you, dear reader. A singly-linked list is
> >simple and straightforward, I find hash-tables ugly and wasteful
> >and will wory about scalability when the time arrives.
>
> IMHO single linked lists do have one drawback: they encode the assumption
> of a specific from of the mapping right into the code. When finally the
> time arrives, the code is usually hard to change. Especially if one does
> not know what exactly the code should do and why a linked list was chosen
> in the first place.

I do not disagree in principle, but in this particular case, the list is both 
the
natural and (relatively) efficient solution. The idea is to push every 
inlining-pair
(identifiers for caller + callee) as a cons onto the list and count the number
of occurrences when walking the list for every new pair. It represents the
inling history directly as it reflects the relative order of inlinings. The 
list is
accessed only twice, once in the search/test and once when pushing a new
pair onto the history, so if one is inclined to change the representation,
it shouldn't be too hard.

The performance penalty for searching the list is in the subsecond area
in my tests (DEBUGBUILD, compiling irregex-core.scm), comparing a version with
the list-search and the current HEAD, irregex-core.scm has about 1500
inlined procedures.

>
> I for one, tend to use balanced trees instead of plain lists when I worry
> about the downsides of hash tables (about those latter I share your view
> Felix) and still want to have obvious and clear code and retain the ability
> to change the implementation.

Balanced trees are nice, but have to be coded with care. In this case it
would probably not make a difference, unless run on files with a
pathological number of inline cases.

So the simplest solution here seems to be sufficient in terms of speed,
minimal in terms of storage used and easiest in terms of maintenance.
That looks appropriate to me.


felix




reply via email to

[Prev in Thread] Current Thread [Next in Thread]