The goal of this document is to compare the performances of some of the existing packages.

  • dequer 2.0-1implements double ended queues and it supports arbitrary R objects. However, it uses R_PreserveObject and R_ReleaseObject heavily which could be an issue for long queues.
  • datastructures 0.2.8 uses ‘Boost’ and ‘STL’ data types to implement queues and hashmaps. For some reasons, it is often slow as shown in the benchmark.
  • liqueueR 0.0.1 implements queues in pure R code which explains its slowness.
  • hash 2.2.6.1 uses R environments to create hash tables. It is known that regular R enviroments leak memory.
  • fastmap 1.0.1. The current implementation of collection::dict is actually inspired by it. However, a more efficient hash table library tommy is used.
  • We also compare to serveral base R implementations based on lists or environments, see here for details.

Queue

Stack

Deque

Priority Queue

Dictionary

Note that base::new.env suffers from memory leak issue. The performance gap between R environments and collections::dict is mainly attributed to the overhead in accessing the $get and $set methods from the dict object.

Ordered dict

Note that ordered_dict grows linearly in n but but list does not.