Home My Page Projects Code Snippets Project Openings SML/NJ Bugs
Summary Activity Tracker Lists

[#40] Very slow compilation with a large statically-defined list

Date:
2009-11-01 19:43
Priority:
3
State:
Open
Submitted by:
Mike Rainey (mrainey)
Assigned to:
David MacQueen (dbm)
Machine Architecture:
None
Operating System:
None
Component:
Compiler
Resolution:
None
Severity:
Minor
OS Version:
SML/NJ Version:
110.70
Keywords:
URL:
Transcript (of reproduction):
Standard ML of New Jersey v110.70 [built: Tue Sep 15 20:12:50 2009] - [opening /Users/mrainey/Downloads/smlnj-bug/smlnj-bug.sml] [autoloading] [library $SMLNJ-BASIS/basis.cm is stable] [autoloading done]
Source (for reproduction):
We attach a compressed version of the source file, as the raw source is too large to put here.
Summary:
Very slow compilation with a large statically-defined list

Detailed description
The attached program takes a very long or possibly infinite time to compile. The problem seems to be in the building of the "runs" list. We noticed that, by shortening the list, compilation would complete quickly. We are able to compile and execute our program in MLton.

Comments:

Message  ↓
Date: 2009-11-05 01:30
Sender: Matthias Blume

This is a well-known problem caused by the way the SML :: operator works. Since it is right-associative but evaluation is strictly left-to-right, long lists can create tremendous register pressure because so many intermediate values have to be held in temporary variables. (In certain cases the compiler could avoid this outright, and in others there are ways of avoiding compile-time blowup at the expense of an extra list reversal or some such, but SML/NJ does not do that in general.)

There is a simple trick for programmers to use (especially if the programmer is a program!):

Define a "reverse cons" operator that is left-associative and takes its arguments in opposite order from ordinary cons. Then generate the source code in reverse order, starting from nil. This will greatly reduce compile time and also be more efficient at runtime.

Date: 2009-11-03 02:29
Sender: George Kuan

That said, the above explanation only addresses the compilation bottleneck. The generated code may also have issues.

Date: 2009-11-03 02:27
Sender: George Kuan

At least from a quick and dirty measurement, the bottleneck appears to be in CPS closure. This problem occurs for any test program that conses a large list in one fell swoop.

Attached Files:

Attachments:
Size Name Date By Download
51 KiBsmlnj-bug.tar.bz22009-11-01 19:43mraineysmlnj-bug.tar.bz2

Changes

Field Old Value Date By
SeverityNone2016-06-30 18:46jhr
assigned_tonone2011-04-08 16:51jhr
File Added2: smlnj-bug.tar.bz22009-11-01 19:43mrainey