Clearly you have a good reason for using BigInts!
OK, I tried with invg and p values that were presumably closer to your use
case (I just generated two random Int128s and then multiplied them as
BigInts). Profiling shows that the problem is indeed in the hashing, as I
suspected. BigInts are definitely not my domain, so I didn't fix the problem,
but here's an issue:
https://github.com/JuliaLang/julia/issues/8727
--Tim
On Saturday, October 18, 2014 06:35:58 AM Michele Zaffalon wrote:
> Hi Tim,
>
> Thank you for the extensive and pedagogical answer (as usual).
>
> > Some questions/tips:
> > - are you doing this at global scope? Put it in a function. See the
> > performance tips section of the manual.
>
> No, both snippets are inside a function.
>
>
> - It looks like you might be storing the result as an Int (0, as in accum
>
> > =>
> > 0, is an Int) in one case and a Float64 in the other case. While it
> > shouldn't
> > make a practical difference in speed, unless there's some reason for that,
> > you
> > probably want to make sure you're comparing them fairly.
>
> My apologies. But as you predicted, changing the declaration to
> lhs = Array(BigInt, 2^20)
> makes no difference: assignment into the array is 2-3 seconds.
>
> > - Have you profiled?
>
> I must admit that I did not do that.
>
> > If you don't actually require BigInts, you definitely shouldn't use
> > them---they
> > will slow your code a lot.
>
> The variables invg and p are integers with more than 100 digits.
>
> > That said, if you need them and want stuff to be
> > fast:
> > - it would be best to look into whether it's possible to implement more
> > efficient hashing.
>
> - even the multiplication of BigInts requires memory allocation. If you're
>
> > desperate for speed, you could consider adding methods to gmp.jl that use
> > a
> > pre-allocated output.
>
> Other students from the course reported that the Python implementation
> takes a couple of seconds using the dictionary.
>
> michele
>
> > On Friday, October 17, 2014 08:31:59 PM Michele Zaffalon wrote:
> > > Hello,
> > >
> > > I am using a dict as a look up table for the result of a computation (it
> >
> > is
> >
> > > for a Coursera class on cryptography if anybody is wondering):
> > >
> > > accum = BigInt(1)
> > > lhs = Dict(accum => 0)
> > > for x1 = 1:2^20-1
> > >
> > > accum = rem(accum * invg, p)
> > > lhs[accum] = x1
> > >
> > > end
> > >
> > > and this takes about 20 seconds on my computer. On the other hand, for
> > > comparison (but not useful for my purpose because I index by the
> >
> > variable
> >
> > > x1), storing the result in an array of preallocated size is about 2
> > > seconds. Here is the code:
> > >
> > > lhs = Array(Float64, 2^20)
> > > for x1 = 1:2^20-1
> > >
> > > accum = rem(accum * invg, p)
> > > lhs[x1] = accum
> > >
> > > end
> > >
> > > Declaring
> > > lhs = Dict{BigInt, Int64}(accum => 0)
> > > does not make any difference.
> > >
> > > Is there a way of preallocating the dictionary of a given size?
> > >
> > > Thank you,
> > > michele
