Mailing-List: contact dev-help@mahout.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@mahout.apache.org
Received-SPF: pass (athena.apache.org: domain of robin.anil@gmail.com
 designates 209.85.128.174 as permitted sender)
MIME-Version: 1.0
In-Reply-To: 
 <CAEccTyyM8=SNBkdmo0qCcGVYy9EkSiBmKhE+gUVXPDj-0d3hdA@mail.gmail.com>
References: <AANLkTi=gbd-GFxpQu_86haq16-gikTrwwZ8x4Tp250jH@mail.gmail.com>
 <AANLkTimxUx-9+_He7XMKGAYMHksGqt3iTbA84Sv8b-9P@mail.gmail.com>
 <AANLkTimgGKApQd=FtBA-bXpr+=b8W-Fg0axC5aUAED6Z@mail.gmail.com>
 <CAB+3LJ=wyaaoMpCdDaBML7N81eqi6c8JTOq+TXp4k8qrK+pCeA@mail.gmail.com>
 <CAM21Rt98Q33BHYDvh+q3Y+zv0G3GvSgwqkspx-u0tB-1SH2thw@mail.gmail.com>
 <CAJwFCa2uGiKNAqesWLMUU9Dhhv9JwOpcq2qiBO7qxsBS9Nvjcg@mail.gmail.com>
 <CAM21Rt8fu6b7XYo7Wg2gX8vy6KBjfwZWwgDwMR0eBNfmLjGXRw@mail.gmail.com>
 <AA19ADD6-555F-410B-BC66-262AE6132AA5@di.unimi.it>
 <CAM21Rt_vXoVPHj99gFNCSyNENV_3X+KCZ=_G-uGMv9Kk5Tm6PA@mail.gmail.com>
 <11CFCC11-4D0F-48B3-A29B-1BD7049F11EA@di.unimi.it>
 <CAM21Rt_PaPF30EQ33aTHjtxTP+kyOX8vi2SLih3S64HT065ZkQ@mail.gmail.com>
 <CAEccTyyugE-HY5aXeWkQWrFBVSoDCx+74VCnndyVghrJqnn8KQ@mail.gmail.com>
 <CAM21Rt9e+ShMpxzSxYiaQvyvp1=O2XVMbHCgQF0raGHcE84TBQ@mail.gmail.com>
 <CAEccTyyM8=SNBkdmo0qCcGVYy9EkSiBmKhE+gUVXPDj-0d3hdA@mail.gmail.com>
From: Robin Anil <robin.anil@gmail.com>
Date: Thu, 6 Jun 2013 03:13:47 +0200
Message-ID: 
 <CAB+3LJmMR+DKrM4o2sAJsP8mWqUqacgUFw_EGoPHfQbKfVvWiA@mail.gmail.com>
Subject: Re: Performance of primitive collections
To: Mahout-Dev <dev@mahout.apache.org>
Content-Type: multipart/alternative; boundary=047d7bb04ce6f1ec2504de720757

--047d7bb04ce6f1ec2504de720757
Content-Type: text/plain; charset=UTF-8

Dawid, could you explain how this is accessing the mahout trunk code? Is
that part of the package step?

Robin Anil | Software Engineer | +1 312 869 2602 | Google Inc.


On Wed, Jun 5, 2013 at 8:20 PM, Sean Owen <srowen@gmail.com> wrote:

> On Wed, Jun 5, 2013 at 7:00 PM, Dawid Weiss
> <dawid.weiss@cs.put.poznan.pl> wrote:
> > 1) if you know your keys are 0...N-1 (dense) then there is typically no
> > need to use a map; you'll do just as well with a regular lookup array :)
>
> Yeah of course... here I think there is no guarantee of this although
> in many practical use cases the keys are drawn from a small range. For
> example 1000 user IDs are often around the range 1 - 1000 or
> something.
>
>
> > Having written the above it made me wonder why Mahout's performance does
> > not drop significantly on those malicious upper-bit changing benchmarks,
> so
> > I checked the code. The thing is Mahout (and I think Colt, originally)
> uses
> > double hashing with prime-sized tables (not 2^n-1 masking) -- this is
> nice
> > and indeed avoids the problems of clustering mentioned in pt. 2 above.
>
> Yes I thought this was why you could largely get away with it. If the
> table is big enough, collisions and chains should not be a big deal to
> begin with.
>
> Since you have this benchmark readily available -- what happens if you
> un-comment one or both of the lines of code that mixes the hash? That
> would really answer it.
>
> i'm curious as I have certainly made this assumption independently in
> the custom hashtable implementations I made long ago (which also use
> double hashing) and still use in the project. If it's not optimal
> that's important info.
>

--047d7bb04ce6f1ec2504de720757--