From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 82195 invoked by alias); 2 Oct 2017 13:05:24 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 82115 invoked by uid 89); 2 Oct 2017 13:05:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.4 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy=hc, unsorted, sneak, HTo:U*palves X-HELO: smtp.polymtl.ca Received: from smtp.polymtl.ca (HELO smtp.polymtl.ca) (132.207.4.11) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 02 Oct 2017 13:05:12 +0000 Received: from simark.ca (simark.ca [158.69.221.121]) (authenticated bits=0) by smtp.polymtl.ca (8.14.7/8.14.7) with ESMTP id v92D56ZG031250 (version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Mon, 2 Oct 2017 09:05:10 -0400 Received: by simark.ca (Postfix, from userid 112) id EF3C91E539; Mon, 2 Oct 2017 09:05:05 -0400 (EDT) Received: from simark.ca (localhost [127.0.0.1]) by simark.ca (Postfix) with ESMTP id 9DEF21E513; Mon, 2 Oct 2017 09:04:54 -0400 (EDT) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit Date: Mon, 02 Oct 2017 13:05:00 -0000 From: Simon Marchi To: Pedro Alves Cc: Tom Tromey , gdb-patches@sourceware.org Subject: Re: [RFA 09/11] Use std::set in mi-main.c In-Reply-To: References: <20170912185736.20436-1-tom@tromey.com> <20170912185736.20436-10-tom@tromey.com> Message-ID: <09eb25b316e1771009f0243829be1fc7@polymtl.ca> X-Sender: simon.marchi@polymtl.ca User-Agent: Roundcube Webmail/1.3.0 X-Poly-FromMTA: (simark.ca [158.69.221.121]) at Mon, 2 Oct 2017 13:05:06 +0000 X-IsSubscribed: yes X-SW-Source: 2017-10/txt/msg00017.txt.bz2 On 2017-09-28 12:10, Pedro Alves wrote: > On 09/12/2017 07:57 PM, Tom Tromey wrote: >> Change a couple of spots in mi-main.c to use std::set. This >> simplifies the code and removes some cleanups. > > std::set always gives me pause. For small objects like int, > and when the use case is insertion phase + lookup phase + discard set, > unsorted inserting into a vector, sorting, and then binary searching > the vector for lookuups is very likely to have better performance, for > cache locality reasons, and also because fewer allocations (with > std::set being a node-based container...) > > But it's likely that in this case it doesn't really matter, so let's > go with the simplicity argument. > > (At some point I may propose some data structure on top of > std::vector for use cases like this.) We have discussed something like this with Sergio in this thread: https://sourceware.org/ml/gdb-patches/2017-07/msg00434.html (you can ctrl-f "boilerplate") We managed to sneak in an std::set while you were not looking/on vacation :). The idea was that the std::set interface really helped to keep the code clean and short, and that we could later implement something with the same behavior and interface as std::set, but based on a vector. It's a bit different than what you propose, because to be a drop-in replacement for a set, we would always keep the vector sorted (insert the new elements where they belong). IIUC, what you propose is to insert everything and then sort it. I think the latter has a better worst-case performance (sorting at the end is n*log(n)) compared to the former (insertion in reverse order will become n^2). I don't think it matters much though, since this data structure would be explicitly for relatively small amount of items. I am not sure if the reasoning is different for a set of string (as in common/environ.{h,c}). I assume it would be similar, since the actual string object is rather small, and when inserting a string in the middle, the following strings will be moved one position and not copied (I haven't verified though). Simon