[{"id":1758711,"web_url":"http://patchwork.ozlabs.org/comment/1758711/","msgid":"","list_archive_url":null,"date":"2017-08-28T16:58:47","subject":"Re: [C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS","submitter":{"id":4423,"url":"http://patchwork.ozlabs.org/api/people/4423/","name":"Michael Matz","email":"matz@suse.de"},"content":"Hi,\n\nOn Mon, 28 Aug 2017, Nathan Sidwell wrote:\n\n> This patch replaces the sorted field vector with a hash map. Lookup for \n> non-function members of a complete class is now O(1), not O(log(n)). \n> We still do linear lookup when the class is incomplete. Fixing that is \n> still on the todo list.\n\nHave you any memory measurement on a non-trivial C++ codebase with many \nclasses (template instantiations?)? On LP64 platforms the sorted list \nfor n members was 8+8*n bytes, the hash-map is 48 bytes itself plus 16*n \nbytes for the entries, where you have at least 13 entries always, next 31, \nnext 61 entries (and so on). You pay the price for the next larger chunk \nalready at about 2/3 fill rate, so e.g a class with 10 members was 88 \nbytes before and is 544 bytes now, which doesn't look that attractive \ngiven that the lookup before took four tries and now takes one, especially \ntaking into account cache effects.\n\n\nCiao,\nMichael.","headers":{"Return-Path":"","X-Original-To":"incoming@patchwork.ozlabs.org","Delivered-To":["patchwork-incoming@bilbo.ozlabs.org","mailing list gcc-patches@gcc.gnu.org"],"Authentication-Results":["ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-461030-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"Fnr6guGV\"; dkim-atps=neutral","sourceware.org; auth=none"],"Received":["from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xgyfS52Bvz9s7m\n\tfor ;\n\tTue, 29 Aug 2017 02:59:11 +1000 (AEST)","(qmail 81352 invoked by alias); 28 Aug 2017 16:59:03 -0000","(qmail 79663 invoked by uid 89); 28 Aug 2017 16:59:01 -0000","from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by\n\tsourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tMon, 28 Aug 2017 16:58:51 +0000","from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254])\tby\n\tmx1.suse.de (Postfix) with ESMTP id 8A78FACF4;\n\tMon, 28 Aug 2017 16:58:48 +0000 (UTC)"],"DomainKey-Signature":"a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:date\n\t:from:to:cc:subject:in-reply-to:message-id:references\n\t:mime-version:content-type; q=dns; s=default; b=kwDt1okPaoFQyar7\n\thBR7WURlOmjURnoa/1J4648pAu5rsnNLEIJWGiqKpa7hQnWPmTn6NssMiKOUSX3d\n\tauAA+YGlTLbRGV6U1sDHprz13hKXkJXPzwb3Dg1naVHVjQIzG8MiThrlK3DFYkGB\n\tOwPAXKpzefMjOJKIOq9/SFRw6NM=","DKIM-Signature":"v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:date\n\t:from:to:cc:subject:in-reply-to:message-id:references\n\t:mime-version:content-type; s=default; bh=iYvJyVm5kleAFOjSTBRkHh\n\t7p+6o=; b=Fnr6guGVuo5ixViw/3kUa8iZ7iFBdwYNSBqn+P8QK90+br7S1GWaD+\n\tUFuU8uWc2dGauLD91qPTY/T6DpPObYGNHWeLuaE537ymK49roarQNsuY9TRZ2gPm\n\tKutpFSVaY/Lm2fInibk/Cs9Wqyr4JKwcR+D8m2FFs95OZ3wEnris8=","Mailing-List":"contact gcc-patches-help@gcc.gnu.org; run by ezmlm","Precedence":"bulk","List-Id":"","List-Unsubscribe":"","List-Archive":"","List-Post":"","List-Help":"","Sender":"gcc-patches-owner@gcc.gnu.org","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-1.9 required=5.0 tests=BAYES_00,\n\tRP_MATCHES_RCVD,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=Hx-languages-length:969,\n\tprice, pay","X-HELO":"mx1.suse.de","Date":"Mon, 28 Aug 2017 18:58:47 +0200 (CEST)","From":"Michael Matz ","To":"Nathan Sidwell ","cc":"GCC Patches ","Subject":"Re: [C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS","In-Reply-To":"<70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org>","Message-ID":"","References":"<70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org>","User-Agent":"Alpine 2.21 (LSU 202 2017-01-01)","MIME-Version":"1.0","Content-Type":"text/plain; charset=US-ASCII","X-IsSubscribed":"yes"}},{"id":1758795,"web_url":"http://patchwork.ozlabs.org/comment/1758795/","msgid":"<06e68d1c-a811-26a0-bf1f-98579c206d8e@acm.org>","list_archive_url":null,"date":"2017-08-28T19:08:28","subject":"Re: [C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS","submitter":{"id":9970,"url":"http://patchwork.ozlabs.org/api/people/9970/","name":"Nathan Sidwell","email":"nathan@acm.org"},"content":"Some quick tests show that memory use increased by 1.5% Compilation \ntime reduced by 1% to 3%\n\nYour comment on IRC about not needing a identifier->decl map, just a \ndecl hash, because the decl already has the identifier is a good one. I \nrecall considering that when converting namespaces, but there the \nanonymous namespace has a NULL name, which is annoying. I just used the \nsame map table here.\n\nHowever, it's probably worth the effort.\n\nIt'd also be nice if the hash table primitive didn't unconditionally \nhold instrumentation counters. AFAICT they only get folded to global \ncounters upon destruction of the hash table. Which for these things \nnever happens.\n\nRemember, when I succeed in folding METHOD_VEC into the same structure, \nwe'll have several members in this table for all but the simplest of \nstructures.\n\nnathan","headers":{"Return-Path":"","X-Original-To":"incoming@patchwork.ozlabs.org","Delivered-To":["patchwork-incoming@bilbo.ozlabs.org","mailing list gcc-patches@gcc.gnu.org"],"Authentication-Results":["ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-461044-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"nI2fvFVN\"; dkim-atps=neutral","sourceware.org; auth=none"],"Received":["from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xh1X42kzcz9sNq\n\tfor ;\n\tTue, 29 Aug 2017 05:08:51 +1000 (AEST)","(qmail 83440 invoked by alias); 28 Aug 2017 19:08:42 -0000","(qmail 83424 invoked by uid 89); 28 Aug 2017 19:08:41 -0000","from mail-yw0-f170.google.com (HELO mail-yw0-f170.google.com)\n\t(209.85.161.170) by sourceware.org\n\t(qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tMon, 28 Aug 2017 19:08:31 +0000","by mail-yw0-f170.google.com with SMTP id s187so7081660ywf.2 for\n\t; Mon, 28 Aug 2017 12:08:31 -0700 (PDT)","from ?IPv6:2620:10d:c0a3:20fb:7500:e7fb:4a6f:2254?\n\t([2620:10d:c091:200::1:d19a]) by smtp.googlemail.com with\n\tESMTPSA id z5sm393337ywf.53.2017.08.28.12.08.28\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256\n\tbits=128/128); Mon, 28 Aug 2017 12:08:29 -0700 (PDT)"],"DomainKey-Signature":"a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender\n\t:subject:to:cc:references:from:message-id:date:mime-version\n\t:in-reply-to:content-type:content-transfer-encoding; q=dns; s=\n\tdefault; b=Ge8siBfVV1HwKC8jJ97Hq9ce92ANGciK8EGVl0l/zoffST5tfrQv1\n\tRwMnCylYOmgX+N4ndqSGXQ5Kb5fMuohA/tjreV/v2WmRwMpj8rjd4qFTEGIwQV9E\n\tzQVKHG71fl/ufUUEyBDIcet0mJX5VnJyAAhpGE9h6XlpzcSdpx6+xw=","DKIM-Signature":"v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender\n\t:subject:to:cc:references:from:message-id:date:mime-version\n\t:in-reply-to:content-type:content-transfer-encoding; s=default;\n\tbh=b7VPtWrKntguLnF57d1eorzKC/w=; b=nI2fvFVN2zsiZG+4/0mfXrqXRufp\n\txeplsaUmAf1cTHVMZoIUkGwU4M59Q84l1ehz/KKGB16yOTu42D09pSQ3K8+SZkXN\n\tCbK4Z8clNVCR2rtbVJvIGY0r2j+JG23dyr/l3uLgY+A1DfS2/SPQ4I3DQoWpZUiX\n\toBcBiGnDl/tdasE=","Mailing-List":"contact gcc-patches-help@gcc.gnu.org; run by ezmlm","Precedence":"bulk","List-Id":"","List-Unsubscribe":"","List-Archive":"","List-Post":"","List-Help":"","Sender":"gcc-patches-owner@gcc.gnu.org","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-1.9 required=5.0 tests=BAYES_00,\n\tFREEMAIL_FROM, RCVD_IN_DNSWL_NONE,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=","X-HELO":"mail-yw0-f170.google.com","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net;\n\ts=20161025;\n\th=x-gm-message-state:sender:subject:to:cc:references:from:message-id\n\t:date:user-agent:mime-version:in-reply-to:content-language\n\t:content-transfer-encoding;\n\tbh=TTSB5JPWNsz5GqLws99o4cM648knN116xFEaUHRUlfc=;\n\tb=htrWFEOhUoND2X2ODZ5ovxMR4DgbJONRPTUd2Dav6//Xc8xOM2QQX5b8YZQwzJcjtO\n\tMmRGuzfip53GKXASN1H2SuLKZKFYY/E4OECc4LvtcjQhVuITo0aXSH9H1sO0QZ2Wh0Zz\n\tPFLbXqeq6ezr7NEy/XoFhIXJobwDiB+LnJ1Mm4krACl1glfhYD5LK9eGKg/3J6/XAHLg\n\tkKQu1u7H/ZLityxovkkGe0BBTZ7hCGndQbVMg8VLRV1YIEAR5H2l2b4Ez0gXuJFx6Hge\n\tnW1XEhe+uhyPFIYE9GnZlTV8q6sHqQnRaU8esTL3SMH0XIXRaUlzlJ8RezsXo1oT1ij1\n\t7/jg==","X-Gm-Message-State":"AHYfb5iPnl7NxXHQc6huzN9zG1JOE/YZRvr4qc7ZignI+yoLjwLl+ggP\tq96BeU2QzcY1SA==","X-Received":"by 10.129.78.215 with SMTP id c206mr1395624ywb.107.1503947309449;\n\tMon, 28 Aug 2017 12:08:29 -0700 (PDT)","Subject":"Re: [C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS","To":"Michael Matz ","Cc":"GCC Patches ","References":"<70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org>\n\t","From":"Nathan Sidwell ","Message-ID":"<06e68d1c-a811-26a0-bf1f-98579c206d8e@acm.org>","Date":"Mon, 28 Aug 2017 15:08:28 -0400","User-Agent":"Mozilla/5.0 (X11; Linux x86_64;\n\trv:52.0) Gecko/20100101 Thunderbird/52.2.1","MIME-Version":"1.0","In-Reply-To":"","Content-Type":"text/plain; charset=utf-8; format=flowed","Content-Transfer-Encoding":"7bit"}},{"id":1759158,"web_url":"http://patchwork.ozlabs.org/comment/1759158/","msgid":"","list_archive_url":null,"date":"2017-08-29T09:18:27","subject":"Re: [C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS","submitter":{"id":1765,"url":"http://patchwork.ozlabs.org/api/people/1765/","name":"Richard Biener","email":"richard.guenther@gmail.com"},"content":"On Mon, Aug 28, 2017 at 9:08 PM, Nathan Sidwell wrote:\n> Some quick tests show that memory use increased by 1.5% Compilation time\n> reduced by 1% to 3%\n>\n> Your comment on IRC about not needing a identifier->decl map, just a decl\n> hash, because the decl already has the identifier is a good one. I recall\n> considering that when converting namespaces, but there the anonymous\n> namespace has a NULL name, which is annoying. I just used the same map\n> table here.\n>\n> However, it's probably worth the effort.\n>\n> It'd also be nice if the hash table primitive didn't unconditionally hold\n> instrumentation counters. AFAICT they only get folded to global counters\n> upon destruction of the hash table. Which for these things never happens.\n\nThere's some debug methods like ::collision that use the fields.\n\nI think for embedding hash_table it would be nice to subclass it,\nhave hash_table_embed not including those fields / methods and have\nhash_table derive from it. Not sure what to do about things like\nhash_map and hash_set -- either template them on the hash-table\ntype or always use the embed variant and see if sth blows up.\n\nRichard.\n\n> Remember, when I succeed in folding METHOD_VEC into the same structure,\n> we'll have several members in this table for all but the simplest of\n> structures.\n>\n> nathan\n>\n> --\n> Nathan Sidwell","headers":{"Return-Path":"","X-Original-To":"incoming@patchwork.ozlabs.org","Delivered-To":["patchwork-incoming@bilbo.ozlabs.org","mailing list gcc-patches@gcc.gnu.org"],"Authentication-Results":["ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-461068-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"kXwT5Eh4\"; dkim-atps=neutral","sourceware.org; auth=none"],"Received":["from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xhNTW4Htzz9s7c\n\tfor ;\n\tTue, 29 Aug 2017 19:22:54 +1000 (AEST)","(qmail 64011 invoked by alias); 29 Aug 2017 09:20:11 -0000","(qmail 62879 invoked by uid 89); 29 Aug 2017 09:18:41 -0000","from mail-wm0-f54.google.com (HELO mail-wm0-f54.google.com)\n\t(74.125.82.54) by sourceware.org\n\t(qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tTue, 29 Aug 2017 09:18:31 +0000","by mail-wm0-f54.google.com with SMTP id y71so16954691wmd.0 for\n\t; Tue, 29 Aug 2017 02:18:29 -0700 (PDT)","by 10.80.180.249 with HTTP; Tue, 29 Aug 2017 02:18:27 -0700 (PDT)"],"DomainKey-Signature":"a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender\n\t:mime-version:in-reply-to:references:from:date:message-id\n\t:subject:to:cc:content-type; q=dns; s=default; b=pBnChY3ZSAKPaT+\n\tCZK/fdSMJOKhpD71d79W2R18nxoNmiQw3qH2P85q8ua+ybHeK/zZZqTUxXWHUmVt\n\tStp3imv2WTtqsziJgq9lexwIhyW8/GZUNl8QdCS44/4ZxuSvOViOOphP1q78F3gt\n\tpCEYvvcYyyCvZfyyRLCHtbUhpsv8=","DKIM-Signature":"v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender\n\t:mime-version:in-reply-to:references:from:date:message-id\n\t:subject:to:cc:content-type; s=default; bh=Zd9N2yMHk57zRP3G4DVUt\n\tFWkbSk=; b=kXwT5Eh4wBrt55S7Jkbaixuc8k4B4hVoXgMXHrroPJ2pjeqNzUgaP\n\tFbg1lQOBDhCztau/q4nWJkkmpUf5UVSFkYKlnOuyh9+ZmEawuaF/U85Xvc8OGyf0\n\thyzB8G6/Bjcs4Qyjg8HLv3DQhOKYto7GZMdwH+iyQCaiDoG0ambn44=","Mailing-List":"contact gcc-patches-help@gcc.gnu.org; run by ezmlm","Precedence":"bulk","List-Id":"","List-Unsubscribe":"","List-Archive":"","List-Post":"","List-Help":"","Sender":"gcc-patches-owner@gcc.gnu.org","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-1.9 required=5.0 tests=AWL, BAYES_00,\n\tFREEMAIL_FROM, RCVD_IN_DNSWL_NONE,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=H*Ad:U*matz","X-HELO":"mail-wm0-f54.google.com","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net;\n\ts=20161025;\n\th=x-gm-message-state:mime-version:in-reply-to:references:from:date\n\t:message-id:subject:to:cc;\n\tbh=7MRi/rN1f2v6xIXZhgBrTHjGx10bQg47k/T/7S7vFYs=;\n\tb=L5OuerX/OW2t7zr8Cl+rnUyTLuWQ1zDeh9KrpdowjOJlVZD+uCvsqBtKZtFaKvJhmS\n\tOPZVg9py64pPaSB5H8OkHDQZnRtlR8kPyO0bbt4GbjlbXax0Hi41JnD0uaYf5a3P57Xr\n\tRgs4yQXW6RFWh6b00k8+ZS11PfVz12sdFyG7F6BqNzBgPSRHuMexMxDZ58GhjANOqj5Z\n\tFfIbj+PXCe98Ord6ozmtwHpmO6Dc+cYnfCQJYzytMkieaaFI7PznTCSNP4GeZHRl+4AH\n\tUGo3sSsKWIvhdXTrgtAKKRoZR278dlU2hWMS/vvsX86c1x/u3BRf/E3Vl8m9qLtYguf0\n\t8fcg==","X-Gm-Message-State":"AHYfb5gWMQ2outNxJcUOhf5FlmMsQs9jb2xERAYAlESMIr/p+l4Px+Hw\taWNRdM8f/kIl7/Os7RVwIxKjEZNY+g==","X-Received":"by 10.80.149.92 with SMTP id v28mr3052348eda.292.1503998307355;\n\tTue, 29 Aug 2017 02:18:27 -0700 (PDT)","MIME-Version":"1.0","In-Reply-To":"<06e68d1c-a811-26a0-bf1f-98579c206d8e@acm.org>","References":"<70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org>\n\t\n\t<06e68d1c-a811-26a0-bf1f-98579c206d8e@acm.org>","From":"Richard Biener ","Date":"Tue, 29 Aug 2017 11:18:27 +0200","Message-ID":"","Subject":"Re: [C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS","To":"Nathan Sidwell ","Cc":"Michael Matz , GCC Patches ","Content-Type":"text/plain; charset=\"UTF-8\"","X-IsSubscribed":"yes"}}]