22
$\begingroup$

Consider the following three data structures: a list of rules, an association, and a dataset:

 n = 1000000;
 list = (ToString[#] -> #) & /@ Range[n];
 assoc = Association@list;
 dataset = Dataset@assoc;

When I try to look up an element "1000000", I get radically different run times:

 ns = ToString[n];
 {ns /. list // AbsoluteTiming, assoc[ns] // AbsoluteTiming, dataset[ns] // AbsoluteTiming}

The results are:

{{0.090609, 1000000}, {5.*10^-6, 1000000}, {0.000237, 1000000}}

Why is Dataset so much slower than Association?

$\endgroup$
  • $\begingroup$ If you have 10.1 could you use RepeatedTiming for a more accurate result? $\endgroup$ – Sjoerd C. de Vries Apr 10 '15 at 22:22
  • 2
    $\begingroup$ No one in their right mind would have a ruleset of that size and not take advantage of Dispatch ... $\endgroup$ – ciao Apr 10 '15 at 22:40
  • 2
    $\begingroup$ @SjoerdC.deVries {Absolute} vs {Repeated timings} : {{0.083047, 6.*10^-6, 0.000307}, {0.082, 3.6*10^-7, 0.00012}} $\endgroup$ – Gordon Coale Apr 10 '15 at 22:52
  • 2
    $\begingroup$ I believe this is answered by WReach here: (57093). Basically Dataset has a larger overhead for each individual call. Even though Query is not used directly I believe the same process is still applied to the arguments of the Dataset, e.g. Dataset`CompileQuery["1000000"] // Trace $\endgroup$ – Mr.Wizard Apr 11 '15 at 1:37
  • $\begingroup$ Its worth noting that on this data Dataset is actually fractionally faster than Association for Select operations when you use RepeatedTimings. Which suggests the "overhead" W Reach describes below is already coming in useful. $\endgroup$ – Gordon Coale Apr 13 '15 at 5:40
16
$\begingroup$

As @Mr.Wizard notes in a comment, some discussion about the overheads associated with querying can be found in another question (56609).

This response will use Mathematica version 10.1.0 to examine the specific behaviour described in the present question. The general principles under discussion are the same for the various 10.0.x versions, but some details differ between releases.

I'll start by showing my timings of the original expressions and along with a few others that will be examined later:

Needs["GeneralUtilities`"]

Function[, {HoldForm[#], AccountingForm @ First @ RepeatedTiming[#;, 1]}, HoldAll] /@
  Unevaluated @
    { ns /. list
    , assoc[ns]
    , dataset[ns]
    , dataset[]
    , Slice[ns][assoc]
    , StrictSlice[ns][assoc]
    } // TableForm

(*
   ns /. list               0.191
   assoc[ns]                0.00000063
   dataset[ns]              0.000149
   dataset[]                0.0000479
   Identity                 0.00000018
   Slice[ns][assoc]         0.00000455
   StrictSlice[ns][assoc]   0.00000239
*)

The expression dataset[] evaluates an no-op query (Identity) upon the dataset. The runtime associated with an Identity operation is negligible, yet the time taken to execute dataset[] is almost a third of the time necessary to compute dataset[ns]. This time is consumed by various overheads associated with query execution, including such things as:

  • query compilation
  • data type deduction
  • dataset validation
  • dataset information caching
  • operator interpretation and rewriting
  • non-standard expression evaluation
  • PartBehavior, MissingBehavior, FailureAction handling
  • all of the myriad standard expression evaluations that occur while implementing these features

These overheads are absent when the operation is performed using a "bare" association.

If we compile the dataset query, we see that it resolves to an invocation of GeneralUtilities`Slice:

Query[ns] // Normal

(* GeneralUtilities`Slice *)

As the timings show, this function has more overhead than a direct application of an association. This is because it implements the default PartBehavior of queries.

We can eliminate that particular overhead by turning it off explicitly:

Query[ns, PartBehavior -> None] // Normal

(* GeneralUtilities`StrictSlice *)

The timings show that StrictSlice has less overhead than Slice, but it is still slower than a direct application of an association (which to all appearances seems to be a built-in kernel operation). If the query compilation process were sensitive to the exact data, it could replace StrictSlice with such a direct application, but the present implementation does not do that.

All of the queries considered in this question execute very quickly, and thus the overheads introduced by Dataset are proportionately very large. But if the queries were long-running (say, a second or more), then the overhead would be insignificant. However, this does mean that if one is going to run a large number of fast-running queries, it might make sense to avoid using Dataset or Query. Alternatively, we might seek ways to replace many small queries with one large query.

We are thus faced with a design decision whether to enjoy the notational convenience of Dataset in exchange for the runtime overhead. We can get closer to the best of both worlds if we precompile a query once using Query[...] // Normal, and then apply the resulting function many times to the data directly.

In closing, I will note that the Dataset / Query machinery gathers a lot of interesting metadata about the data and operations to be performed. The 10.0 and 10.1 implementations presently do not make much use of this metadata when compiling and executing queries. I (wishfully) expect some future release of Mathematica to put all of this metadata to better use. It could be used to make better operator selections, as mentioned with respect to StrictSlice earlier, or to store data within Dataset objects in high-performance data structures. When (if) that happens, then we will have the convenience of Dataset notation and the query execution overheads might not only pay for themselves but return dividends as well.

$\endgroup$
  • 4
    $\begingroup$ That is an incredibly well written answer. Thank you. I'll note that 10.1 uses a simple optimization for Slice: it first tries to use Part to execute the slice, and if that fails, it falls back on a recursive implementation in top level. That should make Slice and StrictSlice almost identical in performance, so in 10.1+ there is no real performance benefit for setting PartBehavior->None. $\endgroup$ – Taliesin Beynon Apr 15 '15 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.