From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8977 Path: news.gmane.org!not-for-mail From: Ed Schouten Newsgroups: gmane.linux.lib.musl.general Subject: Re: Re: AVL tree: storing balances instead of heights Date: Thu, 10 Dec 2015 14:12:08 +0100 Message-ID: References: <20151207130344.GZ23362@port70.net> <20151207144621.GA23362@port70.net> <20151210121449.GC23362@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1449753150 15114 80.91.229.3 (10 Dec 2015 13:12:30 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 10 Dec 2015 13:12:30 +0000 (UTC) To: musl@lists.openwall.com, Ed Schouten Original-X-From: musl-return-8990-gllmg-musl=m.gmane.org@lists.openwall.com Thu Dec 10 14:12:29 2015 Return-path: 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 ) id 1a711E-0004dh-1e for gllmg-musl@m.gmane.org; Thu, 10 Dec 2015 14:12:24 +0100 Original-Received: (qmail 16357 invoked by uid 550); 10 Dec 2015 13:12:21 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 16336 invoked from network); 10 Dec 2015 13:12:20 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nuxi-nl.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=Y4Pe1NkSWQ1P+Q+9Z30Ix8pwozvuBCHxtEDHkZ60Vmw=; b=VFnkrzmVYlaAnzvJffu5+yB6vetI91I0Dce2wl6tnoFeBiunwppCoxmhwLdAZtYIK/ 0j4ir4Z/dY7pUpt2/kCANX36ixcM1zQ9U3DlfQfdQYz3CZlfxw9yc8enaotzG3bvGhPY t1U6PjPxwbpW0EJmiEtC/xzaq+7jO/fiAMNjTOT/z/2l6exp58u/78AOUT36jIc7d2pS qORhzQA3ZhuEDFodhOoFgorJ6y2BlC4l3nh30D4etMigZpHj/syOMDsAhG+fOAgJ5LaD N/DU+O29ITWJxL7XVnCmJgu9bElwaUiB1xu+eqoaOke69Wo1nM9cjnvb22vBwQOoLJhu aEXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:content-type; bh=Y4Pe1NkSWQ1P+Q+9Z30Ix8pwozvuBCHxtEDHkZ60Vmw=; b=Y4grr+/JIOxO5y4gJ2xjldkSJVdykcq6WqOIoKhfEkQuL8jqkwWe72k49ChqgvFC3k +ity93kJJjtq/WiGxX/ILxBHiERZ9ko9WPRjtYPdi2KfJu5RX4PP7ZyCfzZpwcEfqkrU /6CZi+QWzZC4wTR7Ps7ehNyzS7ndFzw3AadpNa36FK8zT7TyD86cDw2gWFxwv08D788F Bv4kPJFjbpAU6A2k0Q4DsneBGFdGM0oKjmVFxGRCOMYPY4xzzz5LbU+tH2wch0FOHGfr euASEUGqJA5duQf3e58zC4lx59p8ol49wziN5oa1dHCLGdNHe1o73AkvUNG6qJDg8mu+ Y6AA== X-Gm-Message-State: ALoCoQkqlePgTC/mAdzfkfQ23/ylk2XhuqUQliztLhTpZsG3F7iQUNX8y3TuRi32bcQ9TzFj4QZG6sasnh46+tYJs5gUisapTQ== X-Received: by 10.129.133.2 with SMTP id v2mr4485968ywf.76.1449753128108; Thu, 10 Dec 2015 05:12:08 -0800 (PST) In-Reply-To: <20151210121449.GC23362@port70.net> Xref: news.gmane.org gmane.linux.lib.musl.general:8977 Archived-At: Hi Szabolcs, 2015-12-10 13:14 GMT+01:00 Szabolcs Nagy : > can you add code size column as well? > (sum of size of x86_64 pic .text+.data+.bss) I've added text sizes for all of the functions, building them using these compilers: GCC: (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010 Clang: 3.7.0-2ubuntu1 (tags/RELEASE_370/final) (based on LLVM 3.7.0) None of the functions use any data/bss, so I've only added the text sizes. As some implementations have some code reuse between tsearch() and tdelete(), I've done both separate and combined builds of these two functions. The sizes of the glibc implementation is an estimate, as I didn't build that one manually. > i assume freebsd does not balance the tree so it timeouts > (which also shows why this api is not useful in practice) Exactly. > glibc uses red-black trees which do less balancing operations > so insert/delete may be faster, but lookup is slightly slower. > (but it seems it does more comparisions and that can be slow) Yes. Comparisons are rather expensive (one callback per comparison), so we'd better optimize for a tree that is as flat as possible. > i assume the musl code there already has the tdelete balancing > patch applied and it is compiled with -Os. It was the latest version in Git, using -O2. > 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(). -- Ed Schouten Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717