From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-Status: No, score=-3.8 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id DFF9A1F55B for ; Wed, 13 May 2020 01:48:24 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 9C90B120A7C; Wed, 13 May 2020 10:47:59 +0900 (JST) Received: from xtrwkhkc.outbound-mail.sendgrid.net (xtrwkhkc.outbound-mail.sendgrid.net [167.89.16.28]) by neon.ruby-lang.org (Postfix) with ESMTPS id DDB48120A7B for ; Wed, 13 May 2020 10:47:56 +0900 (JST) Received: by filter0072p3las1.sendgrid.net with SMTP id filter0072p3las1-6642-5EBB51E0-AC 2020-05-13 01:48:16.541236802 +0000 UTC m=+2346380.430957930 Received: from herokuapp.com (unknown) by geopod-ismtpd-3-3 (SG) with ESMTP id HdRXTXJ2SsCSOwz_iAkt5A for ; Wed, 13 May 2020 01:48:16.377 +0000 (UTC) Date: Wed, 13 May 2020 01:48:16 +0000 (UTC) From: matz@ruby.or.jp Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 74069 X-Redmine-Project: ruby-master X-Redmine-Issue-Tracker: Feature X-Redmine-Issue-Id: 16851 X-Redmine-Issue-Author: ana06 X-Redmine-Sender: matz X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: =?us-ascii?Q?bXEIHGfdFwsIlBTndiToCp=2Fmc2rfxRD2sZAksRKJIHWod8ZvNcfjH19xOy1cGm?= =?us-ascii?Q?cqqm9Th0IxqsYTmxoLu5v6Ttxx1sETzs+pBrw4A?= =?us-ascii?Q?2p+lEbwBcr1Q1QylMAsqYMxfs+9fMLmM=2FcZZnS3?= =?us-ascii?Q?mjGpiaF4se8THyH83TSlrYsmqxgDLsf1R8Ds5Hq?= =?us-ascii?Q?db=2FTTHrghI2UH?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 98308 Subject: [ruby-core:98308] [Ruby master Feature#16851] Ruby hashing algorithm could be improved using Tabulation Hashing X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #16851 has been updated by matz (Yukihiro Matsumoto). Interesting!! @ana06 Do you need any help? Matz. ---------------------------------------- Feature #16851: Ruby hashing algorithm could be improved using Tabulation Hashing https://bugs.ruby-lang.org/issues/16851#change-85547 * Author: ana06 (Ana Maria Martinez Gomez) * Status: Open * Priority: Normal ---------------------------------------- I have implemented Linear Probing and Simple tabulation in Ruby: https://github.com/Ana06/ruby/compare/master...Ana06:tabulation_project I tested it using the following code: https://github.com/Ana06/ruby-tabulation/blob/master/benchmark_tabulation.rb It benchmarks the insertion of 600000 elements (by hashing their 64 bits ids) in an empty hash 100 times. Below are the times (in seconds) I got executing this code for different versions of the Ruby code: - master (without Simple Tabulation): 29.68 - master with Linear Probing (without Simple Tabulation): 99.76 - master with Quadratic Probing (without Simple Tabulation): 29.97 - master with Simple Tabulation: 15.76 - master with Linear Probing and Simple Tabulation: 24.23 - **master with Quadratic Probing and Simple Tabulation: 13.73** `master` refers to ruby 2.8.0dev: (2020-05-07T16:22:38Z master 7ded8fd) [x86_64-linux]. I tried with 8 x Intel i5-8265U. Although this is just a prove of concept and not something that could be already use in production, I think it proves the potential of Simple Tabulation to improve current Ruby implementation. It may be worthwhile to explore this idea further. What do you think? I did this as part of a project for my [Advanced Algorithms course](http://www.cs.columbia.edu/~andoni/advancedS20/index.html). For more details check the project report: https://github.com/Ana06/ruby-tabulation/blob/master/latex/RubyTabulation_Project.pdf -- https://bugs.ruby-lang.org/