RE: [igraph] Speed comparison of R and C

[jeremy.raw]

Gabor's point about R doing a lot of copy operations is the basis for my 
earlier comment about manipulating attributes as a vector rather than as 
individual objects.  R does much better if one can manipulate entire vectors of 
atomic types (things that can be moved and copied efficiently at C level), 
rather than repeatedly replacing individual elements (particularly where the 
individual replacements entail copying entire large objects).  That was the 
origin of my performance recommendation of simply using graph edge identifiers 
to index into separate vectors or matrices of numeric or integer types.

On the other hand, even if one simply does things the "R way" using the vector 
attribute access mechanisms in igraph, the performance still ends up 
dramatically improved.  I've attached a short script that revises the original 
R test, and demonstrates orders of magnitude speed improvement in attribute 
management, even though it looks like more copying of "objects" is taking place.
 
The output of that script follows, where the "First Round" is the original 
function, and the "Second Round" is a new function that performs similar 
operations but uses vectors of attributes rather than accessing them indirectly 
one at a time.

Original Version Start Time: 1297264024
Original Version End Time: 1297264307
Original Elapsed (seconds): 282.483
New Version Start Time: 1297264307
New Version End Time: 1297264307
New Version Elapsed (seconds): 0.04700017
Number of edges: 44850

I may have misunderstood the point of the original code as I made the faster 
version; but this code should demonstrate that there is an opportunity for 
enormous speed improvement by "thinking in R".

Jeremy

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Gábor Csárdi
Sent: Tuesday, February 08, 2011 6:06 PM
To: Help for igraph users
Subject: Re: [igraph] Speed comparison of R and C

On Tue, Feb 8, 2011 at 9:25 PM, Tamás Nepusz <address@hidden> wrote:
> Hi,
>
> Here's an explanation about what's going on behind the scenes. Basically, g 
> <- set.edge.attribute(g, "cap", index=x, value=x) makes a *copy* of the graph 
> object in every iteration of the for loop; set.edge.attribute always copies 
> the graph first, applies the modification to the copy and assigns it back to 
> g. I conjecture that this operation causes most of the overhead. As I'm not 
> too familiar with R, I don't know why it works this way -- maybe Gabor can 
> shed light on it.

Very simple explanation. This is how R works. Not just with igraph
graphs, but with (almost) every other object as well. Functions don't
modify their arguments.

Of course it is possible to circumvent this, but that does not really
make sense, because then igraph would behave VERY differently than all
other R code.

So, yeah, igraph is not too good if your graph changes a lot. Not just
attributes, but deleting/adding vertices/edges individually is also
relatively slow.

Gabor

> However, depending on your use-case, there might be more efficient ways of 
> doing things in R. For instance, your current for loop basically retrieves an 
> edge attribute once for every edge. Instead of that, you could simply write 
> E(g)$load to retrieve the values of the "load" edge attribute for all the 
> edges at once, and this is much faster.  Similarly, you can use E(g)$cap <- 
> capacities to assign to all the edge attributes at once, and this is also 
> much faster.
>
> --
> Tamas
>
>
> On 8 Feb 2011, at 20:38, William Tu wrote:
>
>> Sorry guys,
>>
>> My updated rw_speed.R.
>>
>> William
>>
>> On Tue, Feb 8, 2011 at 2:24 PM, William Tu <address@hidden> wrote:
>>> Hi Tamas,
>>>
>>> Thanks for all the advices. I've attached my C and R code.
>>>
>>> btw, is this the correct way to reply to the mailing list? I click the
>>> "reply via email to" button below the discussion page.
>>>
>>> William
>>>
>>>
>> <rw_speed.R>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM

_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help

rw_speed.R
Description: rw_speed.R