220 36231 <8fbf9854-fb12-4d5a-888f-464d14e5e706@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: Arthur O'Dwyer Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Any plan out there to add a real hash map to the standard? Date: Thu, 21 Dec 2017 17:16:51 -0800 (PST) Lines: 183 Approved: news@gmane.org Message-ID: <8fbf9854-fb12-4d5a-888f-464d14e5e706@isocpp.org> References: <3945078.WOE4bWxDhs@tjmaciei-mobl1> <3efdfdc2-94c3-4ec0-a08f-15f20ff26cae@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_2143_1046756556.1513905411409" X-Trace: blaine.gmane.org 1513905302 16280 195.159.176.226 (22 Dec 2017 01:15:02 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 22 Dec 2017 01:15:02 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDLZJYWNDQIIJOXR2ECRUBF44OKGK@isocpp.org Fri Dec 22 02:14:57 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-vk0-f72.google.com ([209.85.213.72]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eSBvN-0003Wx-Dw for gclcip-std-proposals@m.gmane.org; Fri, 22 Dec 2017 02:14:57 +0100 Original-Received: by mail-vk0-f72.google.com with SMTP id w64sf4013706vkd.12 for ; Thu, 21 Dec 2017 17:16:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=Cv56OjzRjBNe2wpw0Bn9nt+O2UtP4S2L7kf0xYe//bk=; b=cqXNY/1M1p2ysnBoEBljNPa5GolPlPy9N9KDeFYaeMMKi8T77j4xm9Z4EBvHmfM1Vw udA4qIENNqLbIOtkZn+nS3KuwSbPnZie7eqqmUInAEMq3lE1kBxJmWtQlmO68rrkGpnZ hYSKvdtdAwvnG+atE/hVYxJfREJ0FBMcmpMysWA23k8KFNgvep5lSo9VccjriyEg1DgZ VelxJ6h44yvP2B2sTTaqstfunbMefqIe99A4Vn7e9n+pb+S/ZNm3HzRn9apUkAYMF3E8 sOu/xHpR/FQG8nyoZ7H3HbJfnLrOEiK/6gq+KKZjqauDzqCvynRP7I035ZOt/2lNyj1T WH+w== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=Cv56OjzRjBNe2wpw0Bn9nt+O2UtP4S2L7kf0xYe//bk=; b=uEENiJhyR4KJjo7ej/SpyOyIxUTXdo/TJpAHLEjqyVAhweZycEeUZ0Sd/kiFelbmZI aMmKL/SFszwnTYyXeXbBFQA9e1gaLTihUs0JtBGx+ZyJdd+6AvDuugZD4l1Ft/jU/WFS J7H9dy67XuU/XnbmWdgUOYo2l/NdJRMgP/g0O3uXYx3w92oAhn6X8jTAWXXFLVYUohb5 e4/oQp4FePfW9hLmCgzugGifsq9uAIAewuzfdkhTS7R5ORqakOZs0KwQihz0QOEDc5Fi /+yog+1A9f1Vh4cxhcmqdIRmFTKyPK8Jljy6Jp/BZ6cs28SZkALsN372/pMB0ggsLXGT TacQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=Cv56OjzRjBNe2wpw0Bn9nt+O2UtP4S2L7kf0xYe//bk=; b=QAEMZ6T8+np8h3zGFNldV+AIVqDiSs1nUPU7Gn0UD1DrNjxw9lwe0ioUgNMJkdKQ6q rdeoVGldtD1UbT+4xn4ngwUcEUDz0zMHlf2TjB84G5UJJKZH0l2ocORrkG08rCpT7yTD W49OJTDRrZ1RlueYVZQo11UdhghdJ1ZF+5PPhxEgyNirrVPOyV06FIgOVZ13BrzaywkV lMl1899ZIwFhUeAqqSAHcOu8+/LD4V3iYc0o3zeFq2h7OPDXUF+IjMOt4aTyn3Ce7QU2 X+eybqWgbT5hRCRnYI63I+J9kPg6G4FEKqLy6LLX+e0NlkSivsmiMmvQbTmQOVlj8ZrH 264A== X-Gm-Message-State: AKGB3mIB7QeHFZqpc4KJPaGEekV39tTk4JwJPKZM+yQ1ps6wEWXInzZU ZR1Jsr0LEVHy62P9oRivZmwYwg== X-Google-Smtp-Source: ACJfBotvhPssjcE0kORmVnPBTw+YHaSldc2YmA1C//Zf3PBRljCKIrSTvqu0R1up4YmEBDMz/9aFLw== X-Received: by 10.31.21.133 with SMTP id 127mr4622445vkv.119.1513905414586; Thu, 21 Dec 2017 17:16:54 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.176.29.7 with SMTP id j7ls470725uak.15.gmail; Thu, 21 Dec 2017 17:16:52 -0800 (PST) X-Received: by 10.31.192.135 with SMTP id q129mr1149261vkf.0.1513905412051; Thu, 21 Dec 2017 17:16:52 -0800 (PST) In-Reply-To: <3efdfdc2-94c3-4ec0-a08f-15f20ff26cae@isocpp.org> X-Original-Sender: arthur.j.odwyer@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:36231 Archived-At: ------=_Part_2143_1046756556.1513905411409 Content-Type: multipart/alternative; boundary="----=_Part_2144_350237831.1513905411409" ------=_Part_2144_350237831.1513905411409 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thursday, December 21, 2017 at 1:31:25 PM UTC-8, Ben Craig wrote: > > I do not know of any better hash map proposals that are in flight. There= =20 > is a flat map proposal though. > > The main issue with unordered map is that it needs to be implemented with= =20 > link chaining via a linked list per bucket. At best, for a hash miss, yo= u=20 > have one memory lookup (good!), and two lookups for a hash hit (less good= ).=20 > At worst, you need to inspect every element in the bucket, which is usual= ly=20 > going to be one or more cache misses per element. > > Link chaining is a requirement because of the iterator invalidation=20 > guarantees. A rehash is not allowed to invalidate iterators. > More directly, link chaining is a requirement because of the following=20 members of unordered_map: - typename local_iterator - bucket_count() - bucket(const Key&) - bucket_size(size_t) - begin(size_t) - end(size_t) - load_factor() - rehash(size_t) Notice that load_factor() is also the sole reason that unordered_map=20 requires a floating-point unit. =20 > A (typically) faster implementation is to embed the elements in the top= =20 > level array, and then use some probing method for collisions. When=20 > traversing down the collisions, many probing methods will allow the next= =20 > element in the collision chain to be on the same cache line. In the best= =20 > cases, hits and misses can both require just one cache line lookup. In t= he=20 > presence of collisions, you get fewer than N cache lookups. > > This scheme has some drawbacks. Large key / value pairs consume a lot=20 > more memory than with link chaining. Each key type needs two sentinel=20 > values... one for not present and one for recently deleted. > The thing about data structures, IMHO, is that if you really care about=20 their performance you probably won't be happy with *any* product of a=20 committee. Whereas there is a flourishing cottage industry producing data= =20 structure libraries for general use. See for example Google's=20 dense_hash_map and sparse_hash_map; and a quick googling turns up sparsepp,= =20 hopscotch-map, ska::flat_hash_map,... And a special mention to=20 ska::flat_hash_map because its author has written some really nice blog=20 posts = =20 on the subject of hashtable performance and benchmarks (including more=20 hashtable implementations I didn't mention in this paragraph). We can't standardize all of these containers, but at the same time, nothing= =20 prevents you from using them in production today (except natural caution=20 about performance "optimizations" =E2=80=94 and such caution should apply j= ust as=20 gravely to anything coming out of the C++ standard library). The benefit of std::unordered_map is that it provides a relatively=20 hard-to-misuse vocabulary type for storing objects that may not have an=20 efficient (or even possible) "less-than" ordering. It doesn't *need* to be= =20 fast because its primary benefit *is not performance-related*. (Now, I still think unordered_map is stupider than it ought to be, with all= =20 that bucket crap and reliance on float and such; but my complaints pertain= =20 to wanting *less* of the API we *have*, as opposed to wanting a whole=20 nother API to learn *also*.) =E2=80=93Arthur --=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp= ..org/d/msgid/std-proposals/8fbf9854-fb12-4d5a-888f-464d14e5e706%40isocpp.or= g. ------=_Part_2144_350237831.1513905411409 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Thursday, December 21, 2017 at 1:31:25 PM UTC-8, Ben Cr= aig wrote:
I do not know of any= better hash map proposals that are in flight. =C2=A0There is a flat map pr= oposal though.

The main issue with unordered map is that it needs to be i= mplemented with link chaining via a linked list per bucket. =C2=A0At best, = for a hash miss, you have one memory lookup (good!), and two lookups for a = hash hit (less good). At worst, you need to inspect every element in the bu= cket, which is usually going to be one or more cache misses per element.

Link chaining is a requirement because of the iterator invalidation gua= rantees. =C2=A0A rehash is not allowed to invalidate iterators.


More directly, link chaining is a requirement beca= use of the following members of unordered_map:
- typename local_i= terator
- bucket_count()
- bucket(const Key&)
=
- bucket_size(size_t)
- begin(size_t)
- end(si= ze_t)
- load_factor()
- rehash(size_t)

Notice that load_factor() is also the sole reason that unordered_m= ap requires a floating-point unit.

=C2=A0

A (typically) faster implement= ation is to embed the elements in the top level array, and then use some pr= obing method for collisions. =C2=A0When traversing down the collisions, man= y probing methods will allow the next element in the collision chain to be = on the same cache line. =C2=A0In the best cases, hits and misses can both r= equire just one cache line lookup. =C2=A0In the presence of collisions, you= get fewer than N cache lookups.

This scheme has some drawbacks. =C2= =A0Large key / value pairs consume a lot more memory than with link chainin= g. =C2=A0Each key type needs two sentinel values... one for not present and= one for recently deleted.


The thing ab= out data structures, IMHO, is that if you really care about their performan= ce you probably won't be happy with any product of a committee. = Whereas there is a flourishing cottage industry producing data structure li= braries for general use. See for example Google's dense_hash_map and sp= arse_hash_map; and a quick googling turns up sparsepp, hopscotch-map, ska::= flat_hash_map,... And a special mention to ska::flat_hash_map because its a= uthor has written some really nice blog posts on the subject of ha= shtable performance and benchmarks (including more hashtable implementation= s I didn't mention in this paragraph).

We can&= #39;t standardize all of these containers, but at the same time, nothing pr= events you from using them in production today (except natural caution abou= t performance "optimizations" =E2=80=94 and such caution should a= pply just as gravely to anything coming out of the C++ standard library).

The benefit of std::unordered_map is that it provid= es a relatively hard-to-misuse vocabulary type for storing objects that may= not have an efficient (or even possible) "less-than" ordering. I= t doesn't need to be fast because its primary benefit is not = performance-related.

(Now, I still think unord= ered_map is stupider than it ought to be, with all that bucket crap and rel= iance on float and such; but my complaints pertain to wanting less= =C2=A0of the API we have, as opposed to wanting a whole nother API t= o learn also.)

=E2=80=93Arthur

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/8fbf9854-fb12-4d5a-888f-464d14e5e706= %40isocpp.org.
------=_Part_2144_350237831.1513905411409-- ------=_Part_2143_1046756556.1513905411409-- .