Re: [julia-users] Re: Pretty sure Dict (dictionary) is slow

[Isaiah Norton]

You could try ObjectIdDict, which is specialized for this use case.

On Tue, Apr 1, 2014 at 6:51 AM, Freddy Chua <fred...@gmail.com> wrote:

Just to add, the key is an object rather than the usual ASCIIString or Int64

On Tuesday, April 1, 2014 6:34:08 PM UTC+8, Freddy Chua wrote:

I am using Dict to store my values. Since it is hash table, I thought that the performance would remain fairly constant even as the dictionary grows bigger. But this is not what I am experience at the moment. When the size of my Dict grows, the cost of retrieval increases as well. Can someone help me here??? I really need the dictionary to be fast...

[Freddy Chua]

ObjectIdDict does not allow pre-defined types...... wouldn't that affect the performance too?

[Iain Dunning]

Can you give _any_ sample code to demonstrate this behaviour?

[Freddy Chua]

Hard to isolate my code. It may not be the Dictionary as I have also noticed abnormal behaviour with my own customised linked list. I also read in a pretty big chunk of data (1GB).  But let me describe it briefly here.

My program read in some data in the order of 10s of MB

Then it reads in the 1GB data and start processing it, this is the second stage of the program. I ran several tests on this part, sometimes, I read in 10 mb only, sometimes i read in 20mb, sometimes 100 mb. Note, the data in here is independent of one another, it only takes up additional memory in the O/S. So reading in twice the amount of data should only require double the amount of time.

What I discover is, the time spent does not scale linearly, infact, it increases polynomially. I suspect this is due to the way Julia handles data structures and objects with incontiguous memory allocation.

Could someone give some tips on memory management?

[Stefan Karpinski]

If you can provide some example code, lots of people here are more than happy to help performance optimize it, but without example code, it's hard to give you anything more specific than don't allocate more than you have to and don't make copies of things if you don't have to. Using mutating APIs (functions with ! at the end) is helpful. The Dict itself isn't allocating small objects on the heap, but you may very well be generating a lot of garbage along the way.

[Freddy Chua]

type List_Node

bus_stop::Bus_Stop

bus_stops::Dict{Int64, Bus_Stop}

next::List_Node

prev::List_Node

num_next::Int64

num_prev::Int64

distance_to_next::Float64

distance_to_prev::Float64

function List_Node(bus_stop::Bus_Stop)

list_node = new()

list_node.bus_stop = bus_stop

list_node.bus_stops = Dict{Int64, Bus_Stop}()

list_node.bus_stops[bus_stop.id] = bus_stop

list_node.next = list_node

list_node.prev = list_node

list_node.num_next = -1

list_node.num_prev = -1

list_node.distance_to_next = 0.0

list_node.distance_to_prev = 0.0

list_node

end

end

abstract EdgeAbstract

type Bus_Stop

id::Int64

name::ASCIIString

latitude::Float64

longitude::Float64

#edges::ObjectIdDict

edges::Dict{Bus_Stop, EdgeAbstract}

Bus_Stop(id::Int64) = (bs = new(); bs.id = id; bs)

end

type Edge <: EdgeAbstract

src::Bus_Stop

tar::Bus_Stop

speed::Float64

distance::Float64

function Edge(src::Bus_Stop, tar::Bus_Stop, distance::Float64, speed::Float64)

edge = new()

edge.src = src

edge.tar = tar

edge.distance = distance

edge.speed = speed

edge

end

end

function summation_time(origin_node::List_Node, destination_node::List_Node)

    tmp = 0.0

    

    current_node = origin_node

    while current_node != destination_node

        src_bus_stop = current_node.bus_stop 

        tar_bus_stop = current_node.next.bus_stop

        edge = src_bus_stop.edges[tar_bus_stop]

        tmp += edge.distance / edge.speed

    

        current_node = current_node.next

    end

    

    return tmp

end

I noticed calling the summation_time function repeatedly degrades the performance... Anything wrong in what I did ?

[Freddy Chua]

A possible flaw I have is the circular dependency in the data structures between Bus_Stop and Edge.

[Stefan Karpinski]

This code doesn't seem to create a List, Nodes or insert them into a Dict – it just walks over a preexisting linked list.

[Freddy Chua]

I found this, https://groups.google.com/forum/#!searchin/julia-users/garbage/julia-users/6_XvoLBzN60/EHCrT46tIQYJ

Might try to turn off GC and see whether performance improves, will update here later...

[Tim Holy]

One thing to know about is sizehint(). The dict has to rehash when the number
of items exceeds the number of available slots.

--Tim

[Freddy Chua]

Alright, I am pretty certain that 

macro nogc(ex)

  quote

    try

      gc_disable()

      local val = $(esc(ex))

    finally

      gc_enable()

    end

    val

  end

end

Does the trick...

My program does an iterative "gradient descent", a kind of mathematical optimisation algorithm. So I loop through a for loop multiple times. In each loop, nothing gets created or destroyed, so GC is not needed at all. It turns out that turning off GC improves the performance significantly, probably 100x. This issue is serious, I wonder can there be a better way of determining when to call GC. I guessed disabling GC manually is not the intention of the compiler designers..

[Freddy Chua]

Alright, these are my timings are disabling gc

before disabling gc

each for loop takes 911.240040

after disabling gc

each for loop takes 30.351131

around 30x improvement.... and if my loop run 10 times, it would have been a 300x improvement...

I hope julia devs do consider improving the GC invocation...

[Jacob Quinn]

Actually opening an issue is the best way to make sure this gets addressed:

https://github.com/JuliaLang/julia/issues?state=open

[Freddy Chua]

Strange, although my for loop does not create any additional memory, the memory usage increases to 60GB after turning off GC... 

[Isaiah Norton]

There is an open pull request for incremental GC, and Jeff has mentioned that other GC improvements are planned after 0.3 is released.

[Stefan Karpinski]

You still haven't shown any code that actually allocates anything, so it's pretty hard to say why or how that's happening.

[Freddy Chua]

There's a function here where the loop takes place..

https://github.com/JuliaLang/julia/issues/6357#issuecomment-39222296

I don't really allocate anything in the loop..

Freddy Chua

[Tim Holy]

Without looking at your code, I'd guess you have a type problem, and the
allocation is happening because Julia is boxing a variable somewhere.

--Tim

> >>>>>> Dict - it just walks over a preexisting linked list.

[Stefan Karpinski]

That seems most likely.

[Freddy Chua]

abstract EdgeAbstract

type Bus_Stop

id::Int64

edges::Dict{Bus_Stop, EdgeAbstract}

end

type Edge <: EdgeAbstract

src::Bus_Stop

tar::Bus_Stop

speed::Float64

distance::Float64

end

I have isolated the problem. It is this circular dependency that is currently not supported in Julia that causes the loosely typed code and memory allocation problem.

I subsequently remove the circular dependency and the abstract type. Now the code works fast. So I have identified two much needed improvements.. 1) circular dependency support, 2) Garbage collection improvement. Both I believe are already under consideration.