The FASTEST subsets function [Was: Subsets of a list] - comp.lang.scheme

Message from discussion The FASTEST subsets function [Was: Subsets of a list]

John David Stone

View profile

More options Jan 12 2002, 4:18 pm

Newsgroups: comp.lang.scheme

From: John David Stone <st...@cs.grinnell.edu>

Date: 12 Jan 2002 15:18:16 -0600

Local: Sat, Jan 12 2002 4:18 pm

Subject: Re: The FASTEST subsets function [Was: Subsets of a list]

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

o...@pobox.com (o...@pobox.com) writes:
> The benchmark runs in 993 ms of user time and allocates only 36.5 MB
> of memory, on Gambit-C interpreter. This is the absolute, incredible
> record. Under SCM:

> subsets-v3 (called combos by John David Stone)
> ;Evaluation took 1596 mSec (98 in gc) 657662 cells work, 4721364 env, 97 bytes other

> subsets-v5:
> ;Evaluation took 700 mSec (322 in gc) 1708112 cells work, 610264 env, 105 bytes
> other
> That is, more than twice as fast.

Hmm. In my testing environment:

> (time (begin (subsets-v3 (list 1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20) 10) (values)))
(time (begin (subsets-v3 (...) ...) ...))
4 collections
200 ms elapsed cpu time, including 110 ms collecting
195 ms elapsed real time, including 106 ms collecting
4300568 bytes allocated, including 1818144 bytes reclaimed

> (time (begin (subsets-v5 (list 1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20) 10) (values)))
(time (begin (subsets-v5 (...) ...) ...))
12 collections
400 ms elapsed cpu time, including 320 ms collecting
456 ms elapsed real time, including 365 ms collecting
13524544 bytes allocated, including 4595512 bytes reclaimed

That is: Apart from garbage collection, the two procedures are
very closely comparable -- but SUBSETS-V3 creates only a third as much
garbage.

My guess is that, in my testing environment, SUBSETS-V3 is getting
a bigger advantage from Chez Scheme's optimizations. The results I get under
MzScheme are similar to Oleg's:

> (time (begin (subsets-v3 (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) 10) (values)))

cpu time: 1530 real time: 1532 gc time: 580

> (time (begin (subsets-v5 (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) 10) (values)))

cpu time: 640 real time: 635 gc time: 330

John David Stone - Lecturer in Computer Science and Philosophy
Manager of the Mathematics Local-Area Network
Grinnell College - Grinnell, Iowa 50112 - USA
st...@cs.grinnell.edu - http://www.cs.grinnell.edu/~stone/

Reply to author Forward