wrathematics / dequer

A deque for R.

About Me

Software engineer and educator. Spent a decade in the public research space at the intersection of high-performance computing (HPC) and big data analytics. I enjoy thinking about computational linear algebra, GPGPU, HPC and cloud technologies, and open source software development.

I teach a course on the computer science of data science. Sometimes I post my thoughts to the fml blog. I am one of the main developers of the pbdR project for integrating the R language in HPC environments. I also built and maintain the HPCRAN, which is an R package repository for HPC packages.

The best way to contact me is wrathematics at gmail.

Writing Samples

• Matrix Computations in Constrained Memory Environments
• Matrix Factorizations for Data Analysis
• Comparing Symmetric Eigenvalue Performance
• Floating Point Arithmetic Is Hilarious

Recent Publications

• Schmidt, D., 2020, November. A Survey of Singular Value Decomposition Methods for Distributed Tall/Skinny Data. In 2020 IEEE/ACM 11th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA) (pp. 27-34). IEEE.
• Hasan, S.S., Schmidt, D., Kannan, R. and Imam, N., 2019, December. A Scalable Graph Analytics Framework for Programming with Big Data in R (pbdR). In 2019 IEEE International Conference on Big Data (Big Data) (pp. 4783-4792). IEEE.
• Vazhkudai, S.S., de Supinski, B.R., Bland, A.S., Geist, A., Sexton, J., Kahle, J., Zimmer, C.J., Atchley, S., Oral, S., Maxwell, D.E. and Larrea, V.G.V., 2018, November. The design, deployment, and evaluation of the CORAL pre-exascale systems. In SC18: International Conference for High Performance Computing, Networking, Storage and Analysis (pp. 661-672). IEEE.
• Schmidt, D., Chen, W.C., Matheson, M.A. and Ostrouchov, G., 2017. Programming with BIG data in R: Scaling analytics from one to thousands of nodes. Big Data Research, 8, pp.1-11.

dequer's Issues

`as.queue` and related don't work directly on vectors

For instance, if I pass a 3-element vector directly into as.queue, it gives me a queue with 1 element. I would expect it to have 3 elements. For example:

require('dequer')

(as.queue(c(1, 2, 3)))
# A queue with 1 element 

(as.queue(as.list(c(1, 2, 3))))
# A queue with 3 elements

I wonder if this is intended behaviour? As it is, it means I'm having to call as.list on every dataset before I turn it into a queue, which is a bit messy. I don't know if that incurs a performance overhead, however.

How come R is so fast?

Hi,
I've tried your package (which looked promising from the README), but it seems to be slower than just extending the vector by R. Here is the analysis:

f1 <- function(n) {
	library("dequer")
	# s <- stack()
	# for (i in 1:n) push(s, i)
	### str(s)
	# rev(s) # rev works in place
	# unlist(as.list(s))
	q <- queue()
	# for (i in 1:n) pushback(q, i) # too slow
	for (i in 1:n) dequer:::pushback.queue(q, i)	
	# unlist(as.list(q))
	dequer:::as.list.queue(q)
	# dequer:::as.list.deque
}
f1 <- function(n) {
	library("dequer")
	# s <- stack()
	# for (i in 1:n) push(s, i)
	### str(s)
	# rev(s) # rev works in place
	# unlist(as.list(s))
	q <- deque()
	# for (i in 1:n) pushback(q, i) # too slow
	for (i in 1:n) dequer:::pushback.deque(q, i)	
	# unlist(as.list(q))
	dequer:::as.list.deque(q)
	# dequer:::as.list.deque
}
f2 <- function(n) {
	library("dequer") # in case this takes any time, to make the comparison fair
	x <- list()
	for(i in 1:n) x[[i]] <- i
	x
}
library(microbenchmark)
microbenchmark(f1(1000),f2(1000))
microbenchmark(f1(6e5),f2(6e5), times = 1)

output:

> microbenchmark(f1(1000),f2(1000))
Unit: microseconds
     expr      min        lq       mean    median       uq        max neval cld
 f1(1000) 3898.805 4034.1345 14145.7538 4138.5805 4202.055 434272.976   100   b
 f2(1000)  338.326  360.6735   417.8314  383.1765  407.077   3228.053   100  a 
> microbenchmark(f1(6e5),f2(6e5), times = 1)
Unit: milliseconds
      expr       min        lq      mean    median        uq       max neval
 f1(6e+05) 2839.6183 2839.6183 2839.6183 2839.6183 2839.6183 2839.6183     1
 f2(6e+05)  401.9546  401.9546  401.9546  401.9546  401.9546  401.9546     1
> 

Peek at values?

Thanks for the package. R needs more high-performance data structures like this one.

I was surprised that the peek() functions only print the value, not return it. Peeking is a common operation. Is the recommended practice to pop the value, then push it back? It would be great if this wasn't necessary.

Minor typo

Use semantic versioning

Friends don't let friends appear in violation of best practices ;)

Not so fast

Hi.

I tested code from the README and got some interesting results.

library(dequer)

fun1 <- function(n) {
    l <- list()
    for (i in 1:n) l[[i]] <- i
    return(l)
}

# right way to work with loops
fun2 <- function(n) {
    l <- vector(mode = "list", length = n)
    for (i in 1:n) l[[i]] <- i
    return(l)
}

fun3 <- function(n) {
    dl <- deque()
    for (i in 1:n) pushback(dl, i)
    l <- as.list(dl)
    return(l)
}

And comparison:

library(microbenchmark)
n <- c(1e2, 1e3, 1e4)

results <- lapply(n, function(x) microbenchmark(fun1(x), fun2(x), fun3(x), times = 50))
results
[[1]]
Unit: microseconds
    expr     min       lq      mean    median       uq      max neval cld
 fun1(x) 211.449  237.547  268.3748  246.9790  310.202  326.399    50  b 
 fun2(x) 133.002  157.149  176.2252  162.0155  202.334  276.736    50 a  
 fun3(x) 974.118 1018.808 1144.0400 1047.4845 1304.037 1361.196    50   c

[[2]]
Unit: milliseconds
    expr      min       lq      mean   median        uq       max neval cld
 fun1(x) 7.152716 9.402594 16.012337 9.739639 18.960025  63.77235    50   b
 fun2(x) 1.257557 1.429933  2.032583 1.509856  2.036579  10.98680    50  a 
 fun3(x) 9.416961 9.855888 12.951196 9.985354 10.332416 112.30584    50   b

[[3]]
Unit: milliseconds
    expr       min        lq      mean    median         uq       max neval cld
 fun1(x) 633.13061 644.55194 1942.9682 700.27453 2724.14892 13842.183    50   b
 fun2(x)  12.26946  13.07718  262.6274  13.74065   15.11343  2264.404    50  a 
 fun3(x)  96.24794  99.72093 1086.8249 100.34199  105.03587 17598.198    50  ab

We see that dequer wons only with large n. But the preallocation version (fun2()) always faster.

Regards.

Typo in example for rev.r

Should be push(s, i):

dequer can limit length of a queue?

Hello Schmidt,

Thank you for your useful package.

I have one question about usage of dequer, could you answer me?

For example, in python following code generate a queue limiting length of 2 and the queue is rolling updated.

>>> from collections import deque
>>> je_nums = deque(maxlen=2)
>>> gaps = [ ]
>>> for item in data:
         je_nums.append(item)
         if len(je_nums) == 1:
             continue
         if je_nums[1] - je_nums[0] > 1:
                gaps.append(list(je_nums))

Is there a way to achieve the same result in R using dequer?

Thank you so much.