From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Ted Zlatanov Newsgroups: gmane.emacs.help Subject: Re: plists, alists, and hashtables Date: Wed, 05 Aug 2015 14:31:46 -0400 Organization: =?utf-8?B?0KLQtdC+0LTQvtGAINCX0LvQsNGC0LDQvdC+0LI=?= @ Cienfuegos Message-ID: <87oailbn8t.fsf@lifelogs.com> References: <876150vwaa.fsf@mbork.pl> <873803x5q4.fsf@kuiper.lan.informatimago.com> <87a8u7we9s.fsf_-_@lifelogs.com> <02f81836-554f-4bb4-873b-85c24e080e3d@googlegroups.com> <87614uqn5l.fsf@kuiper.lan.informatimago.com> <87d1z2ukw1.fsf@lifelogs.com> <878u9pps1c.fsf@kuiper.lan.informatimago.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1438799729 12072 80.91.229.3 (5 Aug 2015 18:35:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 5 Aug 2015 18:35:29 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Wed Aug 05 20:35:27 2015 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZN3X9-0001vH-Hk for geh-help-gnu-emacs@m.gmane.org; Wed, 05 Aug 2015 20:35:23 +0200 Original-Received: from localhost ([::1]:41686 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZN3X8-0003sK-RL for geh-help-gnu-emacs@m.gmane.org; Wed, 05 Aug 2015 14:35:22 -0400 Original-Path: usenet.stanford.edu!news.tele.dk!news.tele.dk!small.news.tele.dk!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!feeder.erje.net!1.eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 75 Original-X-Trace: news.albasani.net yQYeCOfTIV95KU95GdaRugbKYHNTmixJymfJh+6ql9RuWndnk69uSsUoWw/SrSR8gaNOc0/Msk/MrbD+aireiw== Original-NNTP-Posting-Date: Wed, 5 Aug 2015 18:31:46 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="kDTnanwk/fxl2NiDZxXJZCWCNnF9LfFKwqsFD4bjhOa3byQpKdMfG8F/CAYaGvq5tKvXuj09ydsMsIigMqaa+VXlAiIMoBU1fT03x1GUjFdjPTBaOU4JZ5RZURRucgEF"; mail-complaints-to="abuse@albasani.net" User-Agent: Gnus/5.130012 (Ma Gnus v0.12) Emacs/25.0.50 (gnu/linux) X-Face: bd.DQ~'29fIs`T_%O%C\g%6jW)yi[zuz6; d4V0`@y-~$#3P_Ng{@m+e4o<4P'#(_GJQ%TT= D}[Ep*b!\e,fBZ'j_+#"Ps?s2!4H2-Y"sx" Cancel-Lock: sha1:yBc9lXcprNsJTYmgsLsQWpxk300= sha1:m0QXqQOuZTYAtoOx/hPb9I4WL90= Original-Xref: usenet.stanford.edu gnu.emacs.help:213977 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:106262 Archived-At: On Wed, 05 Aug 2015 19:24:31 +0200 "Pascal J. Bourguignon" wrote: PJB> Ted Zlatanov writes: >> Yes, I think the implicit advantage of everything being a list is well >> understood amongst us. But so is the disadvantage of treating >> everything as a list. The question is whether hashtables, an existing >> ELisp map data type, could become more popular. PJB> Why? To have a true native map data type. PJB> How would that be good? Because a true native map data type avoids the complexity of lists in many cases. PJB> Seriously, hash-tables have a lot of drawbacks. PJB> They use much more memory, PJB> they are much slower (on small dictionaries), I think these details are easily optimized at the C level. Clearly an alist is better as the *backend* hashtable implementation for up to 10, possibly up to 100 entries (depending on caching, pipelining, hashing function, and other factors). But the frontend presentation is what I'm concerned about. I think a better reader syntax for hashtables would make them easier to write and read in code and would error out if they are malformed. That's an improvement over alists and plists I think. PJB> they are much restrictive on the possible key equivalence function. Like I said, 95% of the cases only need eql and equal. For the rest, users can use `make-hash-table' directly instead of through the shortcut syntax. PJB> The only advantage they have, is on speed of access in big dictionaries. PJB> But even when you need a O(1) access on a big dictionary, you will find PJB> you keep converting between hash-table and lists or vectors, of only to PJB> sort the entries out to present them to the user! That's no different than looping over alists and plists to collect and sort the entries, is it? PJB> If you achieved your goal of having unwashed masses use hash-tables "unhashed masses"? :) PJB> instead of a-list/p-lists, the only result you'd attain would be to PJB> slow down emacs. Run your own benchmark. On my computer, I notice PJB> that until the size of the dictionary reaches 20-30, a-lists are PJB> performing better than hash-table. (And even, I call assoc on set, PJB> while for a-list it is customary to just do acons, so inserting or PJB> reseting entries would be even much faster). Absolutely, but I mentioned already that this is easily fixed on the back end. I think it's clear that while hashtables *can* scale, alists and plists *can't* because their backend and frontend are the same. Hashtables are only accessible through an API, their backend is hidden. PJB> Nonetheless, this argument is the reason why the print/read syntax for PJB> hash-tables is: >> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ()) PJB> This extends easily to any other data structure for which you'd want a PJB> literal representation. OK, but still, I'm not interested in heaps, trees, graphs, skip lists, or other data structures. I'm interested in improving the accessibility and popularity of hashtables in order to avoid the complexity and ambiguity of alists and plists when dealing with maps. Ted