From owner-svn-src-all@freebsd.org Sun Aug 7 12:15:30 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id EF4C9BAFB3E for ; Sun, 7 Aug 2016 12:15:30 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: from mail-yw0-x230.google.com (mail-yw0-x230.google.com [IPv6:2607:f8b0:4002:c05::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id ACD331498 for ; Sun, 7 Aug 2016 12:15:30 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mail-yw0-x230.google.com with SMTP id j12so290344157ywb.2 for ; Sun, 07 Aug 2016 05:15:30 -0700 (PDT) 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:from:date:message-id:subject:to :cc; bh=KsPXHo6xtX2YjVMibdBlmv6JedYfknHpCglTP77LKlo=; b=Tyx4Cv1Py6Wmmcd5TIGn4dC5t+pj8UQyF+SDT2vwd0KaULlmSYfPTThOKSxoj316pD Ytu4aNzXxdaINH6gr1OGmT4OoX5HX9wkQTo/wuZeBHBp3spjz/RLk8iTKoujT0imqVCL 2aXHk7vfTmBWnwewAO7ALo1q6BsdZ7mo8VtrIVtk+JXutUde2oOVvYMq4dMlyR+0xeVw 7itCFP3c2aM7ofdWQimo8OGpAg1Ny+wRkStGARWWjPEDYeRwjkRf8OL+pFYzLNM+uN6y UyIiNLpdfiU368K4AwgvlRxL2acDsy5wglN+HyrQz1tFamtRjOe0Fjj1wIk8XBYtWFNK BfFA== 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:from:date :message-id:subject:to:cc; bh=KsPXHo6xtX2YjVMibdBlmv6JedYfknHpCglTP77LKlo=; b=OTs1YQlpANE++ZPqK29oHqGPSU59WVitCF+aHHs8SajgZqVzxvEVCH+X3V8gVmD8tV 9a0Q3yOAj4L38Y8mQ0TCatRZjj88NqmWivIFDvZaIk4dt5no5CUOuH5f60eaiC6ihvhX am5brcfa1dSgg4V/7ji7pXt/H04hGH5y57OC12Df/jtLCimhFuyLPQkmelzz4k/dRRvy EKlnEq/QbtQb7su2PYsHGPP5KABXdAG3F6mlPVB1WiWmEgXEKzBuvx5Hjp4li6He8f8w h4i5T/BPNtyqcqn8zZTvj90H3zyCyFdT01Zfi6deo8V3DHvU37qNs/LTCdZKnsprsVUX cGqw== X-Gm-Message-State: AEkooutzP0zCYBEh150Oz7exzBk+EqQF/9wS8O3kXsRzTHIb+Tr11NOZs/8SVc7KG0fsDjBmAfwR34gVeytczA== X-Received: by 10.129.98.2 with SMTP id w2mr45257730ywb.313.1470572129573; Sun, 07 Aug 2016 05:15:29 -0700 (PDT) MIME-Version: 1.0 Received: by 10.13.201.71 with HTTP; Sun, 7 Aug 2016 05:15:29 -0700 (PDT) In-Reply-To: References: <201608041527.u74FR9xo083057@repo.freebsd.org> <54ec1a67-177b-9fb7-ad2a-b3f371926cc5@FreeBSD.org> From: Ed Schouten Date: Sun, 7 Aug 2016 14:15:29 +0200 Message-ID: Subject: Re: svn commit: r303746 - head/usr.bin/indent To: Piotr Stefaniak Cc: Pedro Giffuni , src-committers , "svn-src-all@freebsd.org" , "svn-src-head@freebsd.org" Content-Type: text/plain; charset=UTF-8 X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Aug 2016 12:15:31 -0000 Hi Piotr, 2016-08-07 10:19 GMT+02:00 Piotr Stefaniak : > The most important conclusion, though, is that at least the glibc > implementation imposes an arbitrary limit on how many items you can add > to the data structure: > The argument nel specifies the maximum number of entries in the table. > (This maximum cannot be changed later, so choose it wisely.) > Adding new items to the data structure (or searching them - I didn't > investigate) actually _stopped working_ when approximately /nel/ number > of elements was reached (I accidentally set it to 2000 while PostgreSQL > has nearly 3000 typedef names). I don't know if FreeBSD's implementation > does the same, but it's a show-stopper to me anyway, so personally I > won't be pursuing this idea of replacing bsearch() with hsearch(). Yeah, that's quite annoying. Both the hsearch() implementation of FreeBSD <11.0 and glibc seem to have a strong disregard of data structure theory. FreeBSD <11.0 uses a fixed size hash table with chaining. glibc also uses a fixed size, but doesn't even do chaining, meaning that there is a hard limit on the number of elements that can be stored. It also becomes incredibly slow by the time it gets close to full. In FreeBSD 11.0 I replaced our implementation by one that runs in constant time per operation (expected and amortised) and also has no fixed limit on the number of elements it can store. In fact, it even ignores the size hint that you provide. Source code: https://svnweb.freebsd.org/base/head/lib/libc/stdlib/hcreate_r.c?view=markup https://svnweb.freebsd.org/base/head/lib/libc/stdlib/hdestroy_r.c?view=markup https://svnweb.freebsd.org/base/head/lib/libc/stdlib/hsearch_r.c?view=markup My guess is that it's faster than bsearch() in this specific case, but if Linux compatibility is important, then I'd say we'd better stick to bsearch(). Thanks for sharing your thoughts! -- Ed Schouten Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717