From mboxrd@z Thu Jan  1 00:00:00 1970
X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8978
Path: news.gmane.org!not-for-mail
From: Szabolcs Nagy <nsz@port70.net>
Newsgroups: gmane.linux.lib.musl.general
Subject: Re: Re: AVL tree: storing balances instead of heights
Date: Thu, 10 Dec 2015 14:43:50 +0100
Message-ID: <20151210134349.GF23362@port70.net>
References: <CABh_MKm1Ow5_dc4ENJM-fAqWc+uPPZgftRdSDxPJiPXZAfZ+FQ@mail.gmail.com>
 <20151207130344.GZ23362@port70.net>
 <CABh_MKnkw_Yp9ifwybXBOMb0FuPvP05T183utZ1kW6Ohqq3gvQ@mail.gmail.com>
 <20151207144621.GA23362@port70.net>
 <CABh_MKmvtxKsMjdzNrqrXQ2VNZ8PMsN=iNd1NRhhrMC6PrYsug@mail.gmail.com>
 <20151210121449.GC23362@port70.net>
 <CABh_MKnwBHOjguKuxvuNCXcZVOuo=DmWEuJRsQCkjrcxCzkbfw@mail.gmail.com>
Reply-To: musl@lists.openwall.com
NNTP-Posting-Host: plane.gmane.org
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: ger.gmane.org 1449755051 14717 80.91.229.3 (10 Dec 2015 13:44:11 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Thu, 10 Dec 2015 13:44:11 +0000 (UTC)
Cc: Ed Schouten <ed@nuxi.nl>
To: musl@lists.openwall.com
Original-X-From: musl-return-8991-gllmg-musl=m.gmane.org@lists.openwall.com Thu Dec 10 14:44:11 2015
Return-path: <musl-return-8991-gllmg-musl=m.gmane.org@lists.openwall.com>
Envelope-to: gllmg-musl@m.gmane.org
Original-Received: from mother.openwall.net ([195.42.179.200])
	by plane.gmane.org with smtp (Exim 4.69)
	(envelope-from <musl-return-8991-gllmg-musl=m.gmane.org@lists.openwall.com>)
	id 1a71Vy-0001f5-55
	for gllmg-musl@m.gmane.org; Thu, 10 Dec 2015 14:44:10 +0100
Original-Received: (qmail 19609 invoked by uid 550); 10 Dec 2015 13:44:02 -0000
Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm
Precedence: bulk
List-Post: <mailto:musl@lists.openwall.com>
List-Help: <mailto:musl-help@lists.openwall.com>
List-Unsubscribe: <mailto:musl-unsubscribe@lists.openwall.com>
List-Subscribe: <mailto:musl-subscribe@lists.openwall.com>
Original-Received: (qmail 19582 invoked from network); 10 Dec 2015 13:44:01 -0000
Mail-Followup-To: musl@lists.openwall.com, Ed Schouten <ed@nuxi.nl>
Content-Disposition: inline
In-Reply-To: <CABh_MKnwBHOjguKuxvuNCXcZVOuo=DmWEuJRsQCkjrcxCzkbfw@mail.gmail.com>
User-Agent: Mutt/1.5.24 (2015-08-30)
Xref: news.gmane.org gmane.linux.lib.musl.general:8978
Archived-At: <http://permalink.gmane.org/gmane.linux.lib.musl.general/8978>

* Ed Schouten <ed@nuxi.nl> [2015-12-10 14:12:08 +0100]:
> 2015-12-10 13:14 GMT+01:00 Szabolcs Nagy <nsz@port70.net>:
> > performance also depends on the allocator since insert/delete
> > has to malloc/free (yet another issue with the api) musl's
> > allocator is i think still better for realtime systems than
> > the jemalloc used in cloudlibc, but it will have worse average
> > performance in benchmarks like this.
> 
> Yes. All of the tests were run on Linux, using glibc. Only the
> tsearch()/tdelete() implementations are different between tests. They
> all use glibc's standard malloc().
> 

ah ok.

based on the updated stats the iterative bottom up
approach seems to be a good tradeoff, i wouldn't
try to reduce stack usage further by increasing the
code size.