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

[Jörg F . Wittenberger]

On Oct 1 2019, address@hidden wrote:

> > I don't think the -unroll-limit is that useful option to expose for the
> > user. The -inline-limit already controls the amount of inlining. I
> > couldn't get anything to unroll more than once without having to
> > increase the inline-limit, which of course has other implications.
>
> The inline-limit considers the _size_ of a procedure to be inlined.
> The unroll-limit specifies the _number_ of times an inlinable procedure
> will actually be inlined at the same call site.
>
> I agree that the declaration/option is of limited use, but it's consisten
> with the declarations/options we have.
>
> > This is unnecessarily O(n^2) in the number of performed inlines. I think
> > we should use a hash-table for inline-history.
> >
> > I tested with some generated files and the results were:
> >
> > Case n=100: real        0m1.784s  vs. real      0m2.179s  (1.2x)
> > Case n=200: real        0m7.495s  vs. real      0m12.235s (1.6x)
> > Case n=300: real        0m17.738s vs. real      0m42.660s (2.4x)
> > Case n=400: real        0m34.975s vs. real      2m3.604s  (3.5x)
>
> 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 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.

So let me suggest to at least not hard code list traversals.

/Jörg