From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA00608; Thu, 5 Jun 2003 18:08:53 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA01869 for ; Thu, 5 Jun 2003 18:08:52 +0200 (MET DST) Received: from epexch01.qlogic.org ([63.170.40.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h55G8pT26383 for ; Thu, 5 Jun 2003 18:08:51 +0200 (MET DST) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Thu, 5 Jun 2003 11:10:15 -0500 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Thu, 5 Jun 2003 11:10:14 -0500 Date: Thu, 5 Jun 2003 11:25:52 -0500 (CDT) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: Alessandro Baretta cc: Ocaml Subject: Re: [Caml-list] Map module In-Reply-To: <3EDF64F9.5020905@baretta.com> Message-ID: MIME-Version: 1.0 Content-Type: MULTIPART/MIXED; BOUNDARY="336237089-55985539-1054830352=:2857" X-OriginalArrivalTime: 05 Jun 2003 16:10:14.0796 (UTC) FILETIME=[F2EB6CC0:01C32B7C] X-Spam: no; 0.00; qlogic:01 caml-list:01 mime-aware:01 docserver:01 alessandro:01 baretta:01 bug:01 struct:01 800000:99 caml:01 int:01 rec:01 folks:01 readable:01 overflow:02 X-Attachments: name="maptest.ml" name="maptest.ml" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. Send mail to mime@docserver.cac.washington.edu for more info. --336237089-55985539-1054830352=:2857 Content-Type: TEXT/PLAIN; charset=US-ASCII On Thu, 5 Jun 2003, Alessandro Baretta wrote: > Hello folks. I've been away for a while. I hope everyone is > well. Long live the Caml! > > Now to the question? > > How well is the Map module supposed to scale into the tens > of thousands of entries? I'm getting a stack overflow when > trying to insert some 80k key-value pairs in a Map. My > function is tail recursive, so I should not be responsibile > for this. > Glancing at the code, it appears to be a height-balanced tree. So operations should use only O(log N) stack frames- call it something less than 32 stack frames for 80K elements. Which means either there is a bug in that code, or your insert routine is not tail-recursive. Attached is a little test program I whipped up to test the map module. I insert 800K elements into a map in the two worst ways I can think of- increasing key order and decreasing key order. I'm actually rather impressed with the performance- running this code only takes a couple of seconds. Which makes me more suspicious that your insert routine isn't tail recursive. Got a code sample you can share? Brian --336237089-55985539-1054830352=:2857 Content-Type: TEXT/PLAIN; charset=US-ASCII; name="maptest.ml" Content-Transfer-Encoding: BASE64 Content-ID: Content-Description: Content-Disposition: attachment; filename="maptest.ml" DQptb2R1bGUgSW50ID0NCiAgICBzdHJ1Y3QNCiAgICAgICB0eXBlIHQgPSBp bnQNCiAgICAgICBsZXQgY29tcGFyZSAoYTogdCkgKGI6IHQpID0gaWYgYSA8 IGIgdGhlbiAtMSBlbHNlIGlmIGEgPiBiIHRoZW4gMSBlbHNlIDANCiAgICBl bmQNCg0KbW9kdWxlIEludE1hcCA9IE1hcC5NYWtlKEludCkNCg0KbGV0IG1h eCA9IDgwMDAwMA0KDQpsZXQgXyA9DQogICAgbGV0IHJlYyBsb29wIG1hcCBh IGIgaSA9DQogICAgICAgIGlmIGkgPCBtYXggdGhlbg0KICAgICAgICAgICAg bG9vcCAoSW50TWFwLmFkZCBpIGEgbWFwKSAoYStiKSBhIChpKzEpDQogICAg ICAgIGVsc2UNCiAgICAgICAgICAgIG1hcA0KICAgIGluDQogICAgbG9vcCAo SW50TWFwLmVtcHR5KSAxIDEgMA0KDQpsZXQgXyA9DQogICAgbGV0IHJlYyBm aWIgYSBiIGkgPQ0KICAgICAgICBpZiBpIDwgbWF4IHRoZW4NCiAgICAgICAg ICAgIGZpYiAoYStiKSBhIChpKzEpDQogICAgICAgIGVsc2UNCiAgICAgICAg ICAgIGEsIGINCiAgICBpbg0KICAgIGxldCByZWMgbG9vcCBtYXAgYSBiIGkg PQ0KICAgICAgICBpZiBpID4gMCB0aGVuDQogICAgICAgICAgICBsb29wIChJ bnRNYXAuYWRkIGkgYSBtYXApIGIgKGEtYikgKGktMSkNCiAgICAgICAgZWxz ZQ0KICAgICAgICAgICAgbWFwDQogICAgaW4NCiAgICBsZXQgYSwgYiA9IGZp YiAxIDEgMCBpbg0KICAgIGxvb3AgKEludE1hcC5lbXB0eSkgYSBiIG1heA0K DQo= --336237089-55985539-1054830352=:2857-- ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners