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

[#51] @ is very slow (quadratic?)

Date:
2009-12-20 17:27
Priority:
3
State:
Closed
Submitted by:
Bug Submitter (webuser)
Assigned to:
John Reppy (jhr)
Machine Architecture:
All
Operating System:
All
Component:
Basis Library
Resolution:
None
Severity:
Minor
OS Version:
SML/NJ Version:
110.71
Keywords:
performance append runtime GC
URL:
Transcript (of reproduction):
measure time of test and test2 on Core2 2.2 Ghz, 2GB RAM, i got 60 and 13 wall-clock seconds.
Source (for reproduction):
fun append l r = let fun app l r = case l of [] => r | (l::ls) => app ls (l::r) in app (rev l) r end ;; fun pow l n = if n>0 then pow (l@l) (n-1) else length l ;; fun pow2 l n = if n>0 then pow2 (append l l) (n-1) else length l ;; fun test () = pow [1] 24 ;; fun test2 () = pow2 [1] 24 ;;
Summary:
@ is very slow (quadratic?)

Detailed description
Append operator @ loses with long lists (test takes 1 minute).
A hand-crafted equivalent wins (test2 takes 13 seconds).
I could not find definition of @, so I am unable to investigate
the problem myself. The problem could be in GC
(there were crazy page fault counts due to very frequent
mappings/unmappings).
(BTW SBCL does the same list-power thing in 6 sec,
GHC in 2 sec, on my machine :)
Submitted via web form by Denis <denis.yevgenyevich@gmail.com>

Comments:

Message  ↓
Date: 2009-12-21 18:00
Sender: John Reppy

Fixed for 110.72.

Attached Files:

Changes

Field Old Value Date By
status_idOpen2009-12-21 18:00jhr
assigned_tonone2009-12-21 18:00jhr
close_date2009-12-21 18:002009-12-21 18:00jhr
Machine Architecturex862009-12-21 18:00jhr
Operating SystemWindows XP2009-12-21 18:00jhr