CODEWITHSUNDEEP
rindexinglookup
cmo
cmo

Reputation: 4104

R lookup time for very long vector

In the R programming language...

Bottleneck in my code:

a  <-  a[b]

where:

This operation is slow: it takes ~ 1.5 - 2.0 seconds.

I thought straightforward indexing would be much faster, even for large vectors.

Am I simply stuck? Or is there a way to speed this up?

Context:

P is a large matrix (10k row, 5k columns).

rows = names, columns = features. values = real numbers.

Problem: Given a subset of names, I need to obtain matrix Q, where:

Here is a naive implementation:

Psub  <-  P[names,]
Q  <-  sapply( Psub , sort )

But I am given 10,000 distinct subsets of names (each subset is several 20% to 90% of the total). Taking the subset and sorting each time is incredibly slow.

Instead, I can pre-compute the order vector:

b  <-  sapply( P , order )

b  <-  convert_to_linear_index( as.data.frame(b) , dim(P) )
# my own function. 
# Now b is a vector of length  nrow(P) * ncol(P)

a  <-  rownames(P)  %in%  myNames
a  <-  rep(a , ncol(P) )

a  <-  a[b]

a  <-  as.matrix(a , nrow = length(myNames) )

Upvotes: 2

Views: 470

Answers (1)

mrip
mrip

Reputation: 15163

I don't see this getting much faster than that. You can try to write an optimized C function to do exactly this, which might cut the time in half or so (and that's optimistic -- vectorized R operations like this don't have much overhead), but not much more than that.

You've got approx 10^8 values to go through. Each time through the internal loop, it needs to increment the iterator, get the index b[i] out of memory, look up a[b[i]] and then save that value into newa[i]. I'm not a compiler/assembly expert by a long shot, but this sounds like on the order of 5-10 instructions, which means you're looking at "big O" of 1 billion instructions total, so there's a clock rate limit to how fast this can go.

Also, R stores logical values as 32 bit ints, so the array a will take up about 400 megs, which doesn't fit into cache, so if b is a more or less random permutation, then you're going to be missing the cache regularly (on most lookups to a, in fact). Again, I'm not an expert, but I would think it's likely that the cache misses here are the bottleneck, and if that's the case, optimized C won't help much.

Aside from writing it in C, the other thing to do is determine whether there are any assumptions you can make that would let you not go through the whole array. For example, if you know most of the indices will not change, and you can figure out which ones do change, you might be able to make it go faster.

On edit, here are some numbers. I have an AMD with clock speed of 2.8GHz. It takes me 3.4 seconds with a random permutation (i.e. lots of cache misses) and 0.7 seconds with either 1:n or n:1 (i.e. very few cache misses), which breaks into 0.6 seconds of execution time and 0.1 of system time, presumably to allocate the new array. So it does appear that cache misses are the thing. Maybe optimized C code could shave something like 0.2 or 0.3 seconds off of that base time, but if the permutation is random, that won't make much difference.

> x<-sample(c(T,F),90*10**6,T)
> prm<-sample(90*10**6)
> prm1<-1:length(prm)
> prm2<-rev(prm1)
> system.time(x<-x[prm])
   user  system elapsed 
  3.317   0.116   3.436 
> system.time(x<-x[prm1])
   user  system elapsed 
  0.593   0.140   0.734 
> system.time(x<-x[prm2])
   user  system elapsed 
  0.631   0.112   0.743 
>

Upvotes: 3

Related Questions