[Ur] compiler time/space depending on number of table attributes

[Adam Chlipala]

The old code used a fold with a function type for the accumulator, as a 
kind of trick to process the schema in reverse order from what would 
happen otherwise. However, the compiler wasn't doing a good job 
optimizing that code.  In particular, every intermediate function would 
up duplicated twice, for exponential code blow-up.  So, instead, I 
reversed the input string and then processed the result in the natural 
order.  Now you can see that the fold accumulator is only referenced 
once, while it was referenced twice before.

On 03/05/2017 11:04 AM, Marko Schütz Schmuck wrote:
> I looked at the diff, but I do not yet understand why the change
> improves the situation.
>
> Could you provide some high-level goal that the change is pursuing? I
> expect that would help me in the future...
>
> Best regards,
>
> Marko
>
> On Sun, 05 Mar 2017 10:51:10 -0400,
> Adam Chlipala wrote:
>> With the extensive compile-time evaluation that comes from Ur/Web's style of
>> metaprogramming, it's not surprising that one would encounter superlinear scaling in time
>> or space, applying components like those in UPO.  I think your conclusion is correct that
>> the type checker isn't to blame. Rather, compile-time reduction was generating exponential
>> explosion in code size.
>>
>> I believe I've fixed the issue, and thanks for reporting it. Don't be surprised to find
>> more in the future!  (I had only tested CSV import with about 5 fields, previously.)
>>
>> On 03/02/2017 04:46 PM, Marko Schütz Schmuck wrote:
>>> Dear All,
>>>
>>> I naïvely tried compiling a source code file with a table having 15
>>> attributes, 3 of which form the key. Also, that table is used with
>>> Csv.importTable from upo.
>>>
>>> After a few seconds the compiler uses 4GB of memory and 100% CPU and
>>> seems stuck. If I reduce the number of attributes to 12 it compiles in
>>> ~2m30s total and with only 4 attributes it's done in ~24s total.
>>>
>>> In this case I actually do not need all the attributes, but for a
>>> future extension I would. I wondered whether the type checker is to
>>> blame, but it appears not: with -tc the compiler takes ~24s total for
>>> the file with the 15 attributes.
>>>
>>> Any recommendations?
>>>
>>> Best regards,
>>>
>>> Marko