Some questions/tips:
- are you doing this at global scope? Put it in a function. See the
performance tips section of the manual.
- 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.
- Have you profiled? I just checked, and a major bottleneck is in hashing the
BigInt value. Much of the time is spent on line 55 of hashing2.jl. There
doesn't seem to be a specialized method available for BigInts; maybe one could
get much better performance with one.
If you don't actually require BigInts, you definitely shouldn't use them---they
will slow your code a lot. 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.
Best,
--Tim
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
