Need very fast application of 'diff' - ideas?

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Need very fast application of 'diff' - ideas?

Kevin Ummel
Hi everyone,

Speed is the key here.

I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.

In R we have:

#Set up input vector
x = runif(n=10e6, min=0, max=1000)
x = round(x)

#Find one-period difference
y = diff(x)

Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...

Many thanks,
Kevin

In iPython:

In [3]: import numpy as np
In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
In [5]: arr1 = arr[1:].view()
In [6]: timeit arr2 = arr1 - arr[:-1]
10 loops, best of 3: 20.1 ms per loop

In Clojure:

(defn subtract-lag
  [n]
  (let [v (take n (repeatedly rand))]
    (time (dorun (map - v (cons 0 v))))))





        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Michael Weylandt
I'd write your own diff() that eliminates the method dispatch and
argument checking that diff -> diff.default does.

x[-1] - x[-len(x)] # is all you really need.
(# you could also try something like c(x[-1], NA) - x which may be
marginally faster as it only subsets x once but you should profile to
find out)

is probably about as fast as you can get within pure R code (the
function overhead will add a little bit of time as well, so if speed
is truly the only thing that matters, best not to use it. If you wanna
go for even more speed, you'll have to go to compiled code; I'd
suggest inline+Rcpp as the easiest way to do so. That could get it
down to a single pass through the vector in pure C (or nice C++) which
seems to be a lower bound for speed.

Michael

On Fri, Jan 27, 2012 at 7:15 PM, Kevin Ummel <[hidden email]> wrote:

> Hi everyone,
>
> Speed is the key here.
>
> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>
> In R we have:
>
> #Set up input vector
> x = runif(n=10e6, min=0, max=1000)
> x = round(x)
>
> #Find one-period difference
> y = diff(x)
>
> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>
> Many thanks,
> Kevin
>
> In iPython:
>
> In [3]: import numpy as np
> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
> In [5]: arr1 = arr[1:].view()
> In [6]: timeit arr2 = arr1 - arr[:-1]
> 10 loops, best of 3: 20.1 ms per loop
>
> In Clojure:
>
> (defn subtract-lag
>  [n]
>  (let [v (take n (repeatedly rand))]
>    (time (dorun (map - v (cons 0 v))))))
>
>
>
>
>
>        [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

plangfelder
In reply to this post by Kevin Ummel
ehm... this doesn't take very many ideas.


x = runif(n=10e6, min=0, max=1000)
x = round(x)

system.time( {
  y = x[-1] - x[-length(x)]
})

I get about 0.5 seconds on my old laptop.

HTH

Peter


On Fri, Jan 27, 2012 at 4:15 PM, Kevin Ummel <[hidden email]> wrote:

> Hi everyone,
>
> Speed is the key here.
>
> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>
> In R we have:
>
> #Set up input vector
> x = runif(n=10e6, min=0, max=1000)
> x = round(x)
>
> #Find one-period difference
> y = diff(x)
>
> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>
> Many thanks,
> Kevin
>
> In iPython:
>
> In [3]: import numpy as np
> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
> In [5]: arr1 = arr[1:].view()
> In [6]: timeit arr2 = arr1 - arr[:-1]
> 10 loops, best of 3: 20.1 ms per loop
>
> In Clojure:
>
> (defn subtract-lag
>  [n]
>  (let [v (take n (repeatedly rand))]
>    (time (dorun (map - v (cons 0 v))))))
>
>
>
>
>
>        [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Hans W Borchers
In reply to this post by Michael Weylandt
R. Michael Weylandt <michael.weylandt <at> gmail.com> writes:

>
> I'd write your own diff() that eliminates the method dispatch and
> argument checking that diff -> diff.default does.
>
> x[-1] - x[-len(x)] # is all you really need.
> (# you could also try something like c(x[-1], NA) - x which may be
> marginally faster as it only subsets x once but you should profile to
> find out)
>
> is probably about as fast as you can get within pure R code (the
> function overhead will add a little bit of time as well, so if speed
> is truly the only thing that matters, best not to use it. If you wanna
> go for even more speed, you'll have to go to compiled code; I'd
> suggest inline+Rcpp as the easiest way to do so. That could get it
> down to a single pass through the vector in pure C (or nice C++) which
> seems to be a lower bound for speed.
>
> Michael


Python has become astonishingly fast during the last years. On an iMAc with
3.06 GHz I can see the following timings (though I do feel a bit suspicious
about the timings Python reports):

    Python      0.040 s     Version 2.6.1, 1e7 integer elements
    Matlab      0.095 s     Matlab's diff function (Version R2011b)
    Matlab      0.315 s     Matlab using x(2:N)-x(1:(N-1))
    R 2.14.1    0.375 s     R's diff() function
    R           0.365 s     R using x[-1]-x[-N]
    R           0.270 s     R using c(x[-1],NA)-x)
    R+Fortran   0.180 s     R function calling .Fortran
    R+C         0.180 s     R function calling .C

where---as an example---the C code looks like:

    void diff(int *n, int *x, int *d)
    { for (long i=0; i<*n-2; i++) d[i] = x[i+1] - x[i]; }

There appears to be a factor of 4 between R+compiled code and Python code.
It is also interesting to see that in Matlab 'diff' is considerably faster
than differencing vectors, while in R it is slower.

P. S.:  To make the comparison fair I have used the following Python call:

    python -m timeit -n 1 -r 1
        -s 'import numpy'
        -s 'arr = numpy.random.randint(0, 1000, (10000000,1)).astype("int32")'
        'diff = arr[1:] - arr[:-1]'

i.e., used 32-bit integers and included the indexing in the loop.


> On Fri, Jan 27, 2012 at 7:15 PM, Kevin Ummel <kevinummel <at> gmail.com> wrote:
> > Hi everyone,
> >
> > Speed is the key here.
> >
> > I need to find the difference between a vector and its one-period lag
> > (i.e. the difference between each value and the subsequent one in the
> > vector). Let's say the vector contains 10 million random integers
> > between 0 and 1,000. The solution vector will have 9,999,999 values,
> > since their is no lag for the 1st observation.
> >
> > In R we have:
> >
> > #Set up input vector
> > x = runif(n=10e6, min=0, max=1000)
> > x = round(x)
> >
> > #Find one-period difference
> > y = diff(x)
> >
> > Question is: How can I get the 'diff(x)' part as fast as absolutely
> > possible? I queried some colleagues who work with other languages, and
> > they provided equivalent solutions in Python and Clojure that, on their
> > machines, appear to be potentially much faster
> > (I've put the code below in case anyone is interested).
> > However, they mentioned that the overhead in passing the data between
> > languages could kill any improvements. I don't have much experience
> > integrating other languages, so I'm hoping the community has some ideas
> > about how to approach this particular problem...
> >
> > Many thanks,
> > Kevin
> >
> > In iPython:
> >
> > In [3]: import numpy as np
> > In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
> > In [5]: arr1 = arr[1:].view()
> > In [6]: timeit arr2 = arr1 - arr[:-1]
> > 10 loops, best of 3: 20.1 ms per loop
> >
> > In Clojure:
> >
> > (defn subtract-lag
> >  [n]
> >  (let [v (take n (repeatedly rand))]
> >    (time (dorun (map - v (cons 0 v))))))
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Kevin Ummel
In reply to this post by plangfelder
Thanks. I've played around with pure R solutions. The fastest re-write of diff (for the 1 lag case) I can seem to find is this:

diff2 = function(x) {
  y = c(x,NA) - c(NA,x)
  y[2:length(x)]
}

#Compiling via 'cmpfun' doesn't seem to help (or hurt):
require(compiler)
diff2 = cmpfun(diff2)

But that only gets ~10% improvement over default 'diff' on my machine. Still too slow for my particular application.

I'm inclined towards Michael's suggestion of inline+Rcpp (or some other use of C under the hood).

Could someone show me how to go about doing that?

Thanks!
Kevin

On Jan 28, 2012, at 9:14 AM, Peter Langfelder wrote:

> ehm... this doesn't take very many ideas.
>
>
> x = runif(n=10e6, min=0, max=1000)
> x = round(x)
>
> system.time( {
>  y = x[-1] - x[-length(x)]
> })
>
> I get about 0.5 seconds on my old laptop.
>
> HTH
>
> Peter
>
>
> On Fri, Jan 27, 2012 at 4:15 PM, Kevin Ummel <[hidden email]> wrote:
>> Hi everyone,
>>
>> Speed is the key here.
>>
>> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>>
>> In R we have:
>>
>> #Set up input vector
>> x = runif(n=10e6, min=0, max=1000)
>> x = round(x)
>>
>> #Find one-period difference
>> y = diff(x)
>>
>> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>>
>> Many thanks,
>> Kevin
>>
>> In iPython:
>>
>> In [3]: import numpy as np
>> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
>> In [5]: arr1 = arr[1:].view()
>> In [6]: timeit arr2 = arr1 - arr[:-1]
>> 10 loops, best of 3: 20.1 ms per loop
>>
>> In Clojure:
>>
>> (defn subtract-lag
>>  [n]
>>  (let [v (take n (repeatedly rand))]
>>    (time (dorun (map - v (cons 0 v))))))
>>
>>
>>
>>
>>
>>        [[alternative HTML version deleted]]
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Dirk Eddelbuettel
In reply to this post by Hans W Borchers

On 28 January 2012 at 16:20, Hans W Borchers wrote:
| R. Michael Weylandt <michael.weylandt <at> gmail.com> writes:
| >
| > I'd write your own diff() that eliminates the method dispatch and
| > argument checking that diff -> diff.default does.
| >
| > x[-1] - x[-len(x)] # is all you really need.
| > (# you could also try something like c(x[-1], NA) - x which may be
| > marginally faster as it only subsets x once but you should profile to
| > find out)
| >
| > is probably about as fast as you can get within pure R code (the
| > function overhead will add a little bit of time as well, so if speed
| > is truly the only thing that matters, best not to use it. If you wanna
| > go for even more speed, you'll have to go to compiled code; I'd
| > suggest inline+Rcpp as the easiest way to do so. That could get it
| > down to a single pass through the vector in pure C (or nice C++) which
| > seems to be a lower bound for speed.
| >
| > Michael
|
|
| Python has become astonishingly fast during the last years. On an iMAc with
| 3.06 GHz I can see the following timings (though I do feel a bit suspicious
| about the timings Python reports):
|
|     Python      0.040 s     Version 2.6.1, 1e7 integer elements
|     Matlab      0.095 s     Matlab's diff function (Version R2011b)
|     Matlab      0.315 s     Matlab using x(2:N)-x(1:(N-1))
|     R 2.14.1    0.375 s     R's diff() function
|     R           0.365 s     R using x[-1]-x[-N]
|     R           0.270 s     R using c(x[-1],NA)-x)
|     R+Fortran   0.180 s     R function calling .Fortran
|     R+C         0.180 s     R function calling .C
|
| where---as an example---the C code looks like:
|
|     void diff(int *n, int *x, int *d)
|     { for (long i=0; i<*n-2; i++) d[i] = x[i+1] - x[i]; }

We looked at a number of these operations in the context of the Rcpp
benchmark for vector convolution.  If you really really care about the last
bit of speed you do a little better using pointer arithmetic rather than [] indexing.

Also, R always checks for NA which is costly.
 
| There appears to be a factor of 4 between R+compiled code and Python code.
| It is also interesting to see that in Matlab 'diff' is considerably faster
| than differencing vectors, while in R it is slower.
|
| P. S.:  To make the comparison fair I have used the following Python call:
|
|     python -m timeit -n 1 -r 1
|         -s 'import numpy'
|         -s 'arr = numpy.random.randint(0, 1000, (10000000,1)).astype("int32")'
|         'diff = arr[1:] - arr[:-1]'
|
| i.e., used 32-bit integers and included the indexing in the loop.

We should be able to close the gap from 40ms for Python to 180ms for R + C. I
suspect there is some room left.  Can you post your codes ?

Dirk
 
 
| > On Fri, Jan 27, 2012 at 7:15 PM, Kevin Ummel <kevinummel <at> gmail.com> wrote:
| > > Hi everyone,
| > >
| > > Speed is the key here.
| > >
| > > I need to find the difference between a vector and its one-period lag
| > > (i.e. the difference between each value and the subsequent one in the
| > > vector). Let's say the vector contains 10 million random integers
| > > between 0 and 1,000. The solution vector will have 9,999,999 values,
| > > since their is no lag for the 1st observation.
| > >
| > > In R we have:
| > >
| > > #Set up input vector
| > > x = runif(n=10e6, min=0, max=1000)
| > > x = round(x)
| > >
| > > #Find one-period difference
| > > y = diff(x)
| > >
| > > Question is: How can I get the 'diff(x)' part as fast as absolutely
| > > possible? I queried some colleagues who work with other languages, and
| > > they provided equivalent solutions in Python and Clojure that, on their
| > > machines, appear to be potentially much faster
| > > (I've put the code below in case anyone is interested).
| > > However, they mentioned that the overhead in passing the data between
| > > languages could kill any improvements. I don't have much experience
| > > integrating other languages, so I'm hoping the community has some ideas
| > > about how to approach this particular problem...
| > >
| > > Many thanks,
| > > Kevin
| > >
| > > In iPython:
| > >
| > > In [3]: import numpy as np
| > > In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
| > > In [5]: arr1 = arr[1:].view()
| > > In [6]: timeit arr2 = arr1 - arr[:-1]
| > > 10 loops, best of 3: 20.1 ms per loop
| > >
| > > In Clojure:
| > >
| > > (defn subtract-lag
| > >  [n]
| > >  (let [v (take n (repeatedly rand))]
| > >    (time (dorun (map - v (cons 0 v))))))
| >
|
| ______________________________________________
| [hidden email] mailing list
| https://stat.ethz.ch/mailman/listinfo/r-help
| PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
| and provide commented, minimal, self-contained, reproducible code.

--
"Outside of a dog, a book is a man's best friend. Inside of a dog, it is too
dark to read." -- Groucho Marx

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Dirk Eddelbuettel

On 28 January 2012 at 11:46, Dirk Eddelbuettel wrote:
|
| On 28 January 2012 at 16:20, Hans W Borchers wrote:
| | R. Michael Weylandt <michael.weylandt <at> gmail.com> writes:
| | >
| | > I'd write your own diff() that eliminates the method dispatch and
| | > argument checking that diff -> diff.default does.
| | >
| | > x[-1] - x[-len(x)] # is all you really need.
| | > (# you could also try something like c(x[-1], NA) - x which may be
| | > marginally faster as it only subsets x once but you should profile to
| | > find out)
| | >
| | > is probably about as fast as you can get within pure R code (the
| | > function overhead will add a little bit of time as well, so if speed
| | > is truly the only thing that matters, best not to use it. If you wanna
| | > go for even more speed, you'll have to go to compiled code; I'd
| | > suggest inline+Rcpp as the easiest way to do so. That could get it
| | > down to a single pass through the vector in pure C (or nice C++) which
| | > seems to be a lower bound for speed.
| | >
| | > Michael
| |
| |
| | Python has become astonishingly fast during the last years. On an iMAc with
| | 3.06 GHz I can see the following timings (though I do feel a bit suspicious
| | about the timings Python reports):
| |
| |     Python      0.040 s     Version 2.6.1, 1e7 integer elements
| |     Matlab      0.095 s     Matlab's diff function (Version R2011b)
| |     Matlab      0.315 s     Matlab using x(2:N)-x(1:(N-1))
| |     R 2.14.1    0.375 s     R's diff() function
| |     R           0.365 s     R using x[-1]-x[-N]
| |     R           0.270 s     R using c(x[-1],NA)-x)
| |     R+Fortran   0.180 s     R function calling .Fortran
| |     R+C         0.180 s     R function calling .C
| |
| | where---as an example---the C code looks like:
| |
| |     void diff(int *n, int *x, int *d)
| |     { for (long i=0; i<*n-2; i++) d[i] = x[i+1] - x[i]; }
|
| We looked at a number of these operations in the context of the Rcpp
| benchmark for vector convolution.  If you really really care about the last
| bit of speed you do a little better using pointer arithmetic rather than [] indexing.
|
| Also, R always checks for NA which is costly.

Ok, couldn't resist.  A _really simple_ Rcpp use case already does _much
better_ relative to R than your R+Fortran and R+C cases:

R> library(inline)
R> library(rbenchmark)
R>
R> X <- seq(1, 1e5)
R>
R> f1 <- function(x) { diff(x) }
R>
R> f2 <- function(x) { x[-1]-x[-length(X)] }
R> stopifnot(all.equal(f1(X), f2(X)))
R>
R> f3 <- function(x) { (x - c(NA, x[-length(X)]))[-1] }
R> stopifnot(all.equal(f1(X), f3(X)))
R>
R> f4 <- cxxfunction(signature(xs="integer"), plugin="Rcpp", body='
+    Rcpp::IntegerVector x(xs);
+    Rcpp::IntegerVector y = diff(x);
+    return y;
+ ')
R> stopifnot(all.equal(f1(X), f4(X)))
R>
R>
R> res <- benchmark("useDiff"     = f1(X),
+                  "firstlast"   = f2(X),
+                  "R vector"    = f3(X),
+                  "Rcpp naive"  = f4(X),
+                  columns=c("test", "elapsed", "relative", "user.self", "sys.self"),
+                  order="relative",
+                  replications=100)
R> print(res)
        test elapsed relative user.self sys.self
4 Rcpp naive   0.013   1.0000     0.012        0
2  firstlast   0.323  24.8462     0.368        0
1    useDiff   0.329  25.3077     0.376        0
3   R vector   0.339  26.0769     0.384        0
R>

That wasn't really trying hard as we didn't do the loops by hand do eliminate
the NA checks etc -- we simply used Rcpp sugar to get vectorised operations
at the C++ level.  I think there is lots of room to make this faster.  (And
yes when I try your Python example on my box, it comes up faster still.)

But this is just to show that

    a) the "compiled" code using Rcpp can be much easier to write than the
       naive (ie Kernighan and Ritchie-inspired) C you put up there

    b) it may beat naive Fortran too as you had a factor of two improvement

    c) a 'factor of 25' improvement for three lines of code is pretty good
       use of programmer's time

Not that f3() needed a fix as the comment "R using c(x[-1],NA)-x)" above does
not lead to the same results as diff(x).

Dirk

 
| | There appears to be a factor of 4 between R+compiled code and Python code.
| | It is also interesting to see that in Matlab 'diff' is considerably faster
| | than differencing vectors, while in R it is slower.
| |
| | P. S.:  To make the comparison fair I have used the following Python call:
| |
| |     python -m timeit -n 1 -r 1
| |         -s 'import numpy'
| |         -s 'arr = numpy.random.randint(0, 1000, (10000000,1)).astype("int32")'
| |         'diff = arr[1:] - arr[:-1]'
| |
| | i.e., used 32-bit integers and included the indexing in the loop.
|
| We should be able to close the gap from 40ms for Python to 180ms for R + C. I
| suspect there is some room left.  Can you post your codes ?
|
| Dirk
|  
|  
| | > On Fri, Jan 27, 2012 at 7:15 PM, Kevin Ummel <kevinummel <at> gmail.com> wrote:
| | > > Hi everyone,
| | > >
| | > > Speed is the key here.
| | > >
| | > > I need to find the difference between a vector and its one-period lag
| | > > (i.e. the difference between each value and the subsequent one in the
| | > > vector). Let's say the vector contains 10 million random integers
| | > > between 0 and 1,000. The solution vector will have 9,999,999 values,
| | > > since their is no lag for the 1st observation.
| | > >
| | > > In R we have:
| | > >
| | > > #Set up input vector
| | > > x = runif(n=10e6, min=0, max=1000)
| | > > x = round(x)
| | > >
| | > > #Find one-period difference
| | > > y = diff(x)
| | > >
| | > > Question is: How can I get the 'diff(x)' part as fast as absolutely
| | > > possible? I queried some colleagues who work with other languages, and
| | > > they provided equivalent solutions in Python and Clojure that, on their
| | > > machines, appear to be potentially much faster
| | > > (I've put the code below in case anyone is interested).
| | > > However, they mentioned that the overhead in passing the data between
| | > > languages could kill any improvements. I don't have much experience
| | > > integrating other languages, so I'm hoping the community has some ideas
| | > > about how to approach this particular problem...
| | > >
| | > > Many thanks,
| | > > Kevin
| | > >
| | > > In iPython:
| | > >
| | > > In [3]: import numpy as np
| | > > In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
| | > > In [5]: arr1 = arr[1:].view()
| | > > In [6]: timeit arr2 = arr1 - arr[:-1]
| | > > 10 loops, best of 3: 20.1 ms per loop
| | > >
| | > > In Clojure:
| | > >
| | > > (defn subtract-lag
| | > >  [n]
| | > >  (let [v (take n (repeatedly rand))]
| | > >    (time (dorun (map - v (cons 0 v))))))
| | >
| |
| | ______________________________________________
| | [hidden email] mailing list
| | https://stat.ethz.ch/mailman/listinfo/r-help
| | PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
| | and provide commented, minimal, self-contained, reproducible code.
|
| --
| "Outside of a dog, a book is a man's best friend. Inside of a dog, it is too
| dark to read." -- Groucho Marx
|
| ______________________________________________
| [hidden email] mailing list
| https://stat.ethz.ch/mailman/listinfo/r-help
| PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
| and provide commented, minimal, self-contained, reproducible code.

--
"Outside of a dog, a book is a man's best friend. Inside of a dog, it is too
dark to read." -- Groucho Marx

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Michael Weylandt
In reply to this post by Kevin Ummel
Have you not followed your own thread? Dirk is Mr. Rcpp himself and he
gives an implementation that gives you 25x improvement here as well as
tips for getting even more out of it:

http://tolstoy.newcastle.edu.au/R/e17/help/12/01/2471.html

Michael

On Sat, Jan 28, 2012 at 12:28 PM, Kevin Ummel <[hidden email]> wrote:

> Thanks. I've played around with pure R solutions. The fastest re-write of diff (for the 1 lag case) I can seem to find is this:
>
> diff2 = function(x) {
>  y = c(x,NA) - c(NA,x)
>  y[2:length(x)]
> }
>
> #Compiling via 'cmpfun' doesn't seem to help (or hurt):
> require(compiler)
> diff2 = cmpfun(diff2)
>
> But that only gets ~10% improvement over default 'diff' on my machine. Still too slow for my particular application.
>
> I'm inclined towards Michael's suggestion of inline+Rcpp (or some other use of C under the hood).
>
> Could someone show me how to go about doing that?
>
> Thanks!
> Kevin
>
> On Jan 28, 2012, at 9:14 AM, Peter Langfelder wrote:
>
>> ehm... this doesn't take very many ideas.
>>
>>
>> x = runif(n=10e6, min=0, max=1000)
>> x = round(x)
>>
>> system.time( {
>>  y = x[-1] - x[-length(x)]
>> })
>>
>> I get about 0.5 seconds on my old laptop.
>>
>> HTH
>>
>> Peter
>>
>>
>> On Fri, Jan 27, 2012 at 4:15 PM, Kevin Ummel <[hidden email]> wrote:
>>> Hi everyone,
>>>
>>> Speed is the key here.
>>>
>>> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>>>
>>> In R we have:
>>>
>>> #Set up input vector
>>> x = runif(n=10e6, min=0, max=1000)
>>> x = round(x)
>>>
>>> #Find one-period difference
>>> y = diff(x)
>>>
>>> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>>>
>>> Many thanks,
>>> Kevin
>>>
>>> In iPython:
>>>
>>> In [3]: import numpy as np
>>> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
>>> In [5]: arr1 = arr[1:].view()
>>> In [6]: timeit arr2 = arr1 - arr[:-1]
>>> 10 loops, best of 3: 20.1 ms per loop
>>>
>>> In Clojure:
>>>
>>> (defn subtract-lag
>>>  [n]
>>>  (let [v (take n (repeatedly rand))]
>>>    (time (dorun (map - v (cons 0 v))))))
>>>
>>>
>>>
>>>
>>>
>>>        [[alternative HTML version deleted]]
>>>
>>> ______________________________________________
>>> [hidden email] mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Kevin Ummel
Sorry, guys. I'm not active on the listserve, so my last post was held by the moderator until after Dirk's solution was posted.

Excellent stuff.

thanks,
kevin

On Jan 29, 2012, at 8:37 AM, R. Michael Weylandt wrote:

> Have you not followed your own thread? Dirk is Mr. Rcpp himself and he
> gives an implementation that gives you 25x improvement here as well as
> tips for getting even more out of it:
>
> http://tolstoy.newcastle.edu.au/R/e17/help/12/01/2471.html
>
> Michael
>
> On Sat, Jan 28, 2012 at 12:28 PM, Kevin Ummel <[hidden email]> wrote:
>> Thanks. I've played around with pure R solutions. The fastest re-write of diff (for the 1 lag case) I can seem to find is this:
>>
>> diff2 = function(x) {
>>  y = c(x,NA) - c(NA,x)
>>  y[2:length(x)]
>> }
>>
>> #Compiling via 'cmpfun' doesn't seem to help (or hurt):
>> require(compiler)
>> diff2 = cmpfun(diff2)
>>
>> But that only gets ~10% improvement over default 'diff' on my machine. Still too slow for my particular application.
>>
>> I'm inclined towards Michael's suggestion of inline+Rcpp (or some other use of C under the hood).
>>
>> Could someone show me how to go about doing that?
>>
>> Thanks!
>> Kevin
>>
>> On Jan 28, 2012, at 9:14 AM, Peter Langfelder wrote:
>>
>>> ehm... this doesn't take very many ideas.
>>>
>>>
>>> x = runif(n=10e6, min=0, max=1000)
>>> x = round(x)
>>>
>>> system.time( {
>>>  y = x[-1] - x[-length(x)]
>>> })
>>>
>>> I get about 0.5 seconds on my old laptop.
>>>
>>> HTH
>>>
>>> Peter
>>>
>>>
>>> On Fri, Jan 27, 2012 at 4:15 PM, Kevin Ummel <[hidden email]> wrote:
>>>> Hi everyone,
>>>>
>>>> Speed is the key here.
>>>>
>>>> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>>>>
>>>> In R we have:
>>>>
>>>> #Set up input vector
>>>> x = runif(n=10e6, min=0, max=1000)
>>>> x = round(x)
>>>>
>>>> #Find one-period difference
>>>> y = diff(x)
>>>>
>>>> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>>>>
>>>> Many thanks,
>>>> Kevin
>>>>
>>>> In iPython:
>>>>
>>>> In [3]: import numpy as np
>>>> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
>>>> In [5]: arr1 = arr[1:].view()
>>>> In [6]: timeit arr2 = arr1 - arr[:-1]
>>>> 10 loops, best of 3: 20.1 ms per loop
>>>>
>>>> In Clojure:
>>>>
>>>> (defn subtract-lag
>>>>  [n]
>>>>  (let [v (take n (repeatedly rand))]
>>>>    (time (dorun (map - v (cons 0 v))))))
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>        [[alternative HTML version deleted]]
>>>>
>>>> ______________________________________________
>>>> [hidden email] mailing list
>>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>>>> and provide commented, minimal, self-contained, reproducible code.
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Michael Weylandt
Sorry about that -- Gmail threaded things by arrival in my mailbox,
not by timestamp (surprisingly)

Rcpp really is one of the coolest new things in the R ecosystem --
hope it works well for you.

M

On Sun, Jan 29, 2012 at 11:12 AM, Kevin Ummel <[hidden email]> wrote:

> Sorry, guys. I'm not active on the listserve, so my last post was held by the moderator until after Dirk's solution was posted.
>
> Excellent stuff.
>
> thanks,
> kevin
>
> On Jan 29, 2012, at 8:37 AM, R. Michael Weylandt wrote:
>
>> Have you not followed your own thread? Dirk is Mr. Rcpp himself and he
>> gives an implementation that gives you 25x improvement here as well as
>> tips for getting even more out of it:
>>
>> http://tolstoy.newcastle.edu.au/R/e17/help/12/01/2471.html
>>
>> Michael
>>
>> On Sat, Jan 28, 2012 at 12:28 PM, Kevin Ummel <[hidden email]> wrote:
>>> Thanks. I've played around with pure R solutions. The fastest re-write of diff (for the 1 lag case) I can seem to find is this:
>>>
>>> diff2 = function(x) {
>>>  y = c(x,NA) - c(NA,x)
>>>  y[2:length(x)]
>>> }
>>>
>>> #Compiling via 'cmpfun' doesn't seem to help (or hurt):
>>> require(compiler)
>>> diff2 = cmpfun(diff2)
>>>
>>> But that only gets ~10% improvement over default 'diff' on my machine. Still too slow for my particular application.
>>>
>>> I'm inclined towards Michael's suggestion of inline+Rcpp (or some other use of C under the hood).
>>>
>>> Could someone show me how to go about doing that?
>>>
>>> Thanks!
>>> Kevin
>>>
>>> On Jan 28, 2012, at 9:14 AM, Peter Langfelder wrote:
>>>
>>>> ehm... this doesn't take very many ideas.
>>>>
>>>>
>>>> x = runif(n=10e6, min=0, max=1000)
>>>> x = round(x)
>>>>
>>>> system.time( {
>>>>  y = x[-1] - x[-length(x)]
>>>> })
>>>>
>>>> I get about 0.5 seconds on my old laptop.
>>>>
>>>> HTH
>>>>
>>>> Peter
>>>>
>>>>
>>>> On Fri, Jan 27, 2012 at 4:15 PM, Kevin Ummel <[hidden email]> wrote:
>>>>> Hi everyone,
>>>>>
>>>>> Speed is the key here.
>>>>>
>>>>> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>>>>>
>>>>> In R we have:
>>>>>
>>>>> #Set up input vector
>>>>> x = runif(n=10e6, min=0, max=1000)
>>>>> x = round(x)
>>>>>
>>>>> #Find one-period difference
>>>>> y = diff(x)
>>>>>
>>>>> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>>>>>
>>>>> Many thanks,
>>>>> Kevin
>>>>>
>>>>> In iPython:
>>>>>
>>>>> In [3]: import numpy as np
>>>>> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
>>>>> In [5]: arr1 = arr[1:].view()
>>>>> In [6]: timeit arr2 = arr1 - arr[:-1]
>>>>> 10 loops, best of 3: 20.1 ms per loop
>>>>>
>>>>> In Clojure:
>>>>>
>>>>> (defn subtract-lag
>>>>>  [n]
>>>>>  (let [v (take n (repeatedly rand))]
>>>>>    (time (dorun (map - v (cons 0 v))))))
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>        [[alternative HTML version deleted]]
>>>>>
>>>>> ______________________________________________
>>>>> [hidden email] mailing list
>>>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>>>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>>>>> and provide commented, minimal, self-contained, reproducible code.
>>>
>>> ______________________________________________
>>> [hidden email] mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: Need very fast application of 'diff' - ideas?

Martin Morgan
In reply to this post by Kevin Ummel
On 01/29/2012 08:12 AM, Kevin Ummel wrote:
> Sorry, guys. I'm not active on the listserve, so my last post was held by the moderator until after Dirk's solution was posted.
>
> Excellent stuff.

Is 'diff' really the bottleneck in your calculations? I would have said
diff was in the class of 'fast' R calculations, so would expect many
other steps in a real analysis, including a poorly constructed input, to
be much more expensive.

Since speed is apparently of the essence, it makes sense to create a
shared library and load that, rather than re-compiling it (via inline)
each time.

The calculation is very straight-forward in C. It makes sense to use the
'.Call' interface to avoid copying on the way in and out, and other R
overhead of the '.C' interface. A simple solution, assuming the correct
argument type (numeric; the original post talks about integer values but
the values actually used (floor(x)) are numeric and presumably in a
speed-is-of-the-essence application the data would be created as the the
type of interest), no NAs, non-0 length input, etc., is (like Hans'
solution, using the .C interface), in file cdiff.c:

#include <Rdefines.h>

SEXP cdiff(SEXP x)
{
     const int len = Rf_length(x) - 1;
     SEXP ans = Rf_allocVector(REALSXP, len);
     double *ansp = REAL(ans), *xp = REAL(x);
     for (int i = 0; i < len; ++i)
         ansp[i] = xp[i + 1] - xp[i];
     return ans;
}

I doubt that, with appropriate optimization flags for the compiler,  use
of [] vs. pointer arithmetic would make a difference. With compilation as

R CMD SHLIB cdiff.c

One would probably want to compile this with a high optimization, e.g.,
from the 'Writing R Extensions' manual section 5.5

MAKEFLAGS="CFLAGS=-O3" R CMD SHLIB cdiff.c

Use as

     dyn.load("cdiff.so")
     ## ...
     x = rnorm(10000000)
     ans <- .Call("cdiff", x)

For me I get

 > dyn.load("cdiff.so")
 > system.time(x <- rnorm(10000000))
    user  system elapsed
   1.577   0.015   1.594
 > system.time(ans0 <- diff(x))
    user  system elapsed
   0.842   0.110   0.952
 > system.time(ans1 <- .Call("cdiff", x))
    user  system elapsed
   0.024   0.020   0.044
 > identical(ans0, ans1)
[1] TRUE

Note that just creating random data already dominates the calculation,
which is why diff seems such an unlikely candidate for a bottleneck. I
would guess that obtaining memory for the answer is the big bottleneck
in cdiff (or Rcpp); one could work around this but then violate R's
memory model. That I can write C code that is 20x faster than 'diff'
comes at a significant price, in terms of error checking and, yes,
development time.

The timing for python in the original post doesn't capture the full cost
of the calculation; it should include the cost of the subset and view
construction (or whatever the efficient pythonic paradigm is)

Martin

>
> thanks,
> kevin
>
> On Jan 29, 2012, at 8:37 AM, R. Michael Weylandt wrote:
>
>> Have you not followed your own thread? Dirk is Mr. Rcpp himself and he
>> gives an implementation that gives you 25x improvement here as well as
>> tips for getting even more out of it:
>>
>> http://tolstoy.newcastle.edu.au/R/e17/help/12/01/2471.html
>>
>> Michael
>>
>> On Sat, Jan 28, 2012 at 12:28 PM, Kevin Ummel<[hidden email]>  wrote:
>>> Thanks. I've played around with pure R solutions. The fastest re-write of diff (for the 1 lag case) I can seem to find is this:
>>>
>>> diff2 = function(x) {
>>>   y = c(x,NA) - c(NA,x)
>>>   y[2:length(x)]
>>> }
>>>
>>> #Compiling via 'cmpfun' doesn't seem to help (or hurt):
>>> require(compiler)
>>> diff2 = cmpfun(diff2)
>>>
>>> But that only gets ~10% improvement over default 'diff' on my machine. Still too slow for my particular application.
>>>
>>> I'm inclined towards Michael's suggestion of inline+Rcpp (or some other use of C under the hood).
>>>
>>> Could someone show me how to go about doing that?
>>>
>>> Thanks!
>>> Kevin
>>>
>>> On Jan 28, 2012, at 9:14 AM, Peter Langfelder wrote:
>>>
>>>> ehm... this doesn't take very many ideas.
>>>>
>>>>
>>>> x = runif(n=10e6, min=0, max=1000)
>>>> x = round(x)
>>>>
>>>> system.time( {
>>>>   y = x[-1] - x[-length(x)]
>>>> })
>>>>
>>>> I get about 0.5 seconds on my old laptop.
>>>>
>>>> HTH
>>>>
>>>> Peter
>>>>
>>>>
>>>> On Fri, Jan 27, 2012 at 4:15 PM, Kevin Ummel<[hidden email]>  wrote:
>>>>> Hi everyone,
>>>>>
>>>>> Speed is the key here.
>>>>>
>>>>> I need to find the difference between a vector and its one-period lag (i.e. the difference between each value and the subsequent one in the vector). Let's say the vector contains 10 million random integers between 0 and 1,000. The solution vector will have 9,999,999 values, since their is no lag for the 1st observation.
>>>>>
>>>>> In R we have:
>>>>>
>>>>> #Set up input vector
>>>>> x = runif(n=10e6, min=0, max=1000)
>>>>> x = round(x)
>>>>>
>>>>> #Find one-period difference
>>>>> y = diff(x)
>>>>>
>>>>> Question is: How can I get the 'diff(x)' part as fast as absolutely possible? I queried some colleagues who work with other languages, and they provided equivalent solutions in Python and Clojure that, on their machines, appear to be potentially much faster (I've put the code below in case anyone is interested). However, they mentioned that the overhead in passing the data between languages could kill any improvements. I don't have much experience integrating other languages, so I'm hoping the community has some ideas about how to approach this particular problem...
>>>>>
>>>>> Many thanks,
>>>>> Kevin
>>>>>
>>>>> In iPython:
>>>>>
>>>>> In [3]: import numpy as np
>>>>> In [4]: arr = np.random.randint(0, 1000, (10000000,1)).astype("int16")
>>>>> In [5]: arr1 = arr[1:].view()
>>>>> In [6]: timeit arr2 = arr1 - arr[:-1]
>>>>> 10 loops, best of 3: 20.1 ms per loop
>>>>>
>>>>> In Clojure:
>>>>>
>>>>> (defn subtract-lag
>>>>>   [n]
>>>>>   (let [v (take n (repeatedly rand))]
>>>>>     (time (dorun (map - v (cons 0 v))))))
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>         [[alternative HTML version deleted]]
>>>>>
>>>>> ______________________________________________
>>>>> [hidden email] mailing list
>>>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>>>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>>>>> and provide commented, minimal, self-contained, reproducible code.
>>>
>>> ______________________________________________
>>> [hidden email] mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.


--
Computational Biology
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N. PO Box 19024 Seattle, WA 98109

Location: M1-B861
Telephone: 206 667-2793

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.