Tree-like data sets with efficient storage and retrieval

Question

Most probably this is going to be a duplicate, sorry. I found too many questions/answers here about tree-like structures, and still could not locate what I want.

It is a followup of my previous question Clever caching of a recursively defined function; I've implemented that according to the very nice answer, but it sort of reached its limit, so now I want something more quick and memory efficient.

I need to compute lots of (integer) values of the form f[n,{a1,...,ak}] which depend on each other in a certain way, so I want to store the intermediate results. Seemingly an optimal way to do it would be a list {F[1],...,F[M]} where each F[n] is a tree-like structure, with F[n][a1] holding the value of f[n,{a1}], together with all F[n][a1][a2] for which f[n,{a1,a2,...}] have been computed, etc. There are several ways to do it that would be very fast at retrieval, but I am not sure how to achieve memory efficiency. I should use some nested Association or Dataset or what?

To be specific, here is what I actually want to compute:

stepreduce[{n_, a_, b_}] :=
 Which[
  b == {} \[Or] n == -1, {n, a, b},
  a == {} \[Or] First[a] < First[b], {n, b, a},
  First[a] == First[b], {If[n == 1, 0, -1], {}, {}},
  True, With[{d = First[a] - First[b], 
    r = Mod[First[b], First[a] - First[b]]},
   {n - First[b], Join[If[r == 0, {d}, {d - r, r}], Rest[a]], Rest[b]}
   ]
  ]

reduce[n_, a_, k_] := Most[FixedPoint[stepreduce, {n, a, {k}}]]

compute[n_, a_] := 
 If[n < 0, 0, 
  If[a == {}, If[n == 0, 1, Sum[compute[n, {k}], {k, n}]], 
   Sum[compute @@ reduce[n, a, k], {k, n}]]]

f[n_] := compute[n, {}]

Thus for example f[3] requires compute[3,{1}], compute[3,{2}] and compute[3,{3}], while compute[3,{1}] and compute[3,{3}] require compute[2,{1,1}], etc.

Answer 1

Simple memoization

There are few places where we can optimize code from OP.

Let's start with already mentioned in OP simplest memoization.

stepreduce // ClearAll
stepreduce@{n_, a_, b_} := Which[
  b == {} \[Or] n == -1,
    {n, a, b},
  a == {} \[Or] First@a < First@b,
    {n, b, a},
  First@a == First@b,
    {If[n == 1, 0, -1], {}, {}},
  True,
    With[{d = First@a - First@b, r = Mod[First@b, First@a - First@b]},
      {n - First@b, Join[If[r == 0, {d}, {d - r, r}], Rest@a], Rest@b}
    ]
]

reduce // ClearAll
reduce[n_, a_, k_] := Most@FixedPoint[stepreduce, {n, a, {k}}]

compute // ClearAll
compute[-1, {}] = 0;
compute[0, {}] = 1;
compute[n_, {}] := compute[n, {}] = Sum[compute[n, {k}], {k, n}]
compute[n_, a_] := compute[n, a] = Sum[compute @@ reduce[n, a, k], {k, n}]

f // ClearAll
f@n_ := compute[n, {}]

Let's gather time and memory usage of above function for calculating first 40 values.

results = <||>;

AppendTo[results, "DownValues memoization" -> Table[
  Internal`InheritedBlock[{compute}, Module[{res},
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ]],
  {i, 40}
]] // Last
(* {{1, 0.000074, 3984}, {2, 0.000121, 4208}, {6, 0.000284, 5136}, {14, 0.000663, 6680},
    {34, 0.001389, 8592}, {68, 0.003436, 11312}, {150, 0.010413, 15192}, {296, 0.014905, 21256},
    {586, 0.017695, 30344}, {1140, 0.025606, 44104}, {2182, 0.051756, 68168}, {4130, 0.072319, 93312},
    {7678, 0.121303, 136872}, {14368, 0.179369, 208728}, {26068, 0.286492, 297072}, {48248, 0.449439, 418840},
    {86572, 0.731423, 627224}, {158146, 1.17463, 878960}, {281410, 1.77709, 1298176}, {509442, 2.57542, 1811608},
    {901014, 4.01303, 2669760}, {1618544, 6.20318, 3717656}, {2852464, 9.20258, 5471776}, {5089580, 13.7751, 7606608},
    {8948694, 21.0816, 11174504}, {15884762, 31.8216, 15514256}, {27882762, 48.4341, 22760552}, {49291952, 71.3518, 31979744},
    {86435358, 108.607, 46273240}, {152316976, 159.118, 64178184}, {266907560, 229.416, 93926304}, {469232204, 337.286, 130198288},
    {821844316, 505.145, 190618272}, {1442300988, 745.747, 264372384}, {2525295380, 1108., 386819480}, {4426185044, 1607.57, 536494800},
    {7747801190, 2397.82, 784631984}, {13567867834, 3492.71, 1088333528}, {23745303556, 5196.81, 1591114776}, {41557384062, 7588.04, 2210837400}} *)

---

reduce compilation

Further speed-up can be gained by compiling reduce function.

We can see that, inside stepreduce, whenever a list can increase it's length, b list decreases it's length. Total length of a and b lists can't grow during reduce call. So we can start with single list $\{n, \, a_m, \, a_{m-1}, \, \ldots, \, a_1, \, b_1 = k\}$, keep track of length and positions of first elements of a and b lists, and of "direction" in which possible change in positions of first elements will move. This way we can perform all steps of reduce without memory reallocation.

Since compiled function can't return ragged arrays, we'll move around single list na containing n as first element and reversed a list as rest of elements.

reduce // ClearAll
reduce = Hold@Compile[{{na, _Integer, 1}, {k, _Integer}},
  Module[{n, aPos, aLen, bPos, bLen, posDelta, nab},
    n = na[[1]];
    aPos = Length@na;
    aLen = aPos - 1;
    bLen = 1;
    bPos = aPos + 1;
    posDelta = 1;
    nab = Append[na, k];
    While[True,
      Which[
        bLen < 1 || n === -1,
          Break[],
        aLen < 1  || nab[[aPos]] < nab[[bPos]],
          With[{aLenOld = aLen, aPosOld = aPos},
            aLen = bLen;
            bLen = aLenOld;
            aPos = bPos;
            bPos = aPosOld;
            posDelta = -posDelta;
          ],
        nab[[aPos]] === nab[[bPos]],
          n = If[n === 1, 0, -1];
          aLen = 0;
          Break[],
        True,
          Module[{bFirst, d, r},
            bFirst = nab[[bPos]];
            d = nab[[aPos]] - bFirst;
            r = Mod[bFirst, d];
            n = n - bFirst;
            If[r === 0,
              nab[[aPos]] = d;
            (* else *),
              nab[[aPos]] = r;
              aPos += posDelta;
              nab[[aPos]] = d - r;
              ++aLen;
            ];
            bPos += posDelta;
            --bLen;
          ]
      ];
    ];
    If[posDelta === -1,
      Module[{max, reverseMax},
        max = Length@nab + 2;
        reverseMax = Quotient[max - 1, 2];
        If[aLen + 1 < reverseMax, reverseMax = aLen + 1];
        Do[
          With[{tmp = nab[[i]], j = max - i},
            nab[[i]] = nab[[j]];
            nab[[j]] = tmp;
          ];,
          {i, 2, reverseMax}
        ]
      ]
    ];
    nab[[1]] = n;
    Take[nab, aLen + 1]
  ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
] /.
  Part -> Compile`GetElement //. HoldPattern[Compile`GetElement@x__ = y_] :> (Part@x = y) //.
  HoldPattern[Plus][pre___, x_, HoldPattern[Times][-1, y_], post___] :> Plus[pre, Subtract[x, y], post] //
  ReleaseHold // Last;

compute // ClearAll
compute@{-1} = 0;
compute@{0} = 1;
compute@na_ := compute@na = With[{n = First@na},
  If[Length@na === 1,
    Sum[compute@{n, k}, {k, n}]
  (* else *),
    Sum[compute@Developer`FromPackedArray@reduce[na, k], {k, n}]
  ]
]

f // ClearAll
f@n_ := compute@{n}

Again time and memory usage:

AppendTo[results, "DownValues memoization + compilation" -> Table[
  Internal`InheritedBlock[{compute}, Module[{res},
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ]],
  {i, 40}
]] // Last
(* {{1, 0.000063, 2832}, {2, 0.000078, 4136}, {6, 0.000091, 5424}, {14, 0.00017, 6720},
    {34, 0.000332, 9376}, {68, 0.000605, 11616}, {150, 0.001157, 15024}, {296, 0.001871, 21344},
    {586, 0.003039, 29936}, {1140, 0.005082, 43944}, {2182, 0.007769, 62952}, {4130, 0.011655, 92952},
    {7678, 0.014263, 136368}, {14368, 0.023007, 195168}, {26068, 0.033489, 287104}, {48248, 0.050387, 408872},
    {86572, 0.075441, 598824}, {158146, 0.101385, 850560}, {281410, 0.140992, 1241104}, {509442, 0.211831, 1820328},
    {901014, 0.32101, 2612696}, {1618544, 0.460999, 3660608}, {2852464, 0.680271, 5414824}, {5089580, 1.19728, 7549832},
    {8948694, 1.50457, 11118344}, {15884762, 2.29116, 15459152}, {27882762, 3.47475, 22708256}, {49291952, 4.49639, 31527560},
    {86435358, 6.61805, 46235728}, {152316976, 9.90871, 64156608}, {266907560, 14.3602, 93992544}, {469232204, 19.7709, 130377928},
    {821844316, 29.5902, 190884312}, {1442300988, 42.7437, 264764776}, {2525295380, 62.8208, 387425584}, {4426185044, 92.3726, 537406200},
    {7747801190, 130.204, 786031768}, {13567867834, 183.552, 1090416752}, {23745303556, 267.809, 1594242360}, {41557384062, 391.204, 2211848640}} *)

---

Caching in a tree

As noted by OP different a lists share many elements, so it might be more memory efficient to store result in a specially constructed tree.

While Associations offer fast appending and random access they're also pretty memory hungry, so might not be the best choice for this memory constrained problem.

Instead I propose to use the fact that "ordinary" compound Mathematica expression is a tree, so we can keep results in an expression such that our na list will be position of either result, or of sub-expression having result as it's head.

Such expression offers fast random access, but appending to a node of $k$ elements is $\mathcal O(k)$ operation. Since nodes won't have more than n elements, this shouldn't have huge performance impact.

integerTreeResizeStep = Function[,
  With[{node = #1},
    Which[
      IntegerQ@node,
        #1 = Array[-1&, #2, 1, node],
      Length@node < #2,
        #1 = Join[node, Array[-1&, #2 - Length@node, 1, Head@node]]
    ];
  ];
  Unevaluated@Unevaluated@#1[[#2]]
  ,
  HoldFirst
];
integerTreeGetOrSetLeaf = Function[{tree, path, value},
  Module[{val},
    val = Quiet@Check[
      Extract[tree, path]
      ,
      Fold[integerTreeResizeStep, Unevaluated@tree, path];
      -1
    ];
    If[Not@IntegerQ@val, val = Head@val];
    If[val < 0,
      val = value;
      If[IntegerQ@Extract[tree, path],
        tree[[Sequence @@ path]] = val
      (* else *),
        tree[[Sequence @@ path, 0]] = val
      ];
    ];
    val
  ],
  HoldAll
];

$cache = {};

compute // ClearAll
compute@{-1} = 0;
compute@{0} = 1;
compute@na_ := integerTreeGetOrSetLeaf[$cache, na,
  With[{n = First@na},
    If[Length@na === 1,
      Sum[compute@{n, k}, {k, n}]
    (* else *),
      Sum[compute@reduce[na, k], {k, n}]
    ]
  ]
]

Time and memory usage:

AppendTo[results, "Tree cache + compilation" -> Table[
  Module[{res},
    $cache = {};
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ],
  {i, 40}
]] // Last
(* {{1, 0.000261, 10176}, {2, 0.000286, 14008}, {6, 0.000478, 17800}, {14, 0.000841, 21712},
    {34, 0.001428, 25624}, {68, 0.002476, 29536}, {150, 0.003977, 33448}, {296, 0.006287, 37360},
    {586, 0.00936, 41272}, {1140, 0.014786, 45184}, {2182, 0.022635, 49096}, {4130, 0.034472, 53016},
    {7678, 0.051892, 56920}, {14368, 0.078604, 60840}, {26068, 0.118647, 64744}, {48248, 0.177518, 68664},
    {86572, 0.25746, 81520}, {158146, 0.381425, 98904}, {281410, 0.558052, 131784}, {509442, 0.816168, 167584},
    {901014, 1.19629, 232680}, {1618544, 1.73458, 305024}, {2852464, 2.53002,  434480}, {5089580, 3.64807, 580352},
    {8948694, 5.27007, 838488}, {15884762, 7.58268, 1130824}, {27882762, 10.9998, 1646504}, {49291952, 15.8523, 2231320},
    {86435358, 23.3352, 3261424}, {152316976, 33.9201, 4431688}, {266907560, 47.8143, 6489776}, {469232204, 69.2132, 8828752},
    {821844316, 99.1624, 12943664}, {1442300988, 143.114, 17620240}, {2525295380, 207.741, 25844920}, {4426185044, 293.7, 35193936},
    {7747801190, 432.95, 51638240}, {13567867834, 618.074, 70324968}, {23745303556, 887.757, 103203720}, {41557384062, 1258.96, 140563328}} *)

---

Sharing nodes

If we examine our $cache we'll see that there's large percentage of nodes containing only zeros. Especially common are nodes that can be created by prepending flat zero node to itself.

Table[Count[$cache, Nest[Prepend[#, #] &, 0 @@ ConstantArray[0, j], i - 1], Infinity], {i, 20}, {j, 40 - 2 i}] // TableForm
Total[%, 2]
(* 2041389 *)

We can reduce memory usage by making sure that, in our cache tree, same zero nodes are internally stored as pointers to single expressions, not as copies of this expression.

We can do this by keeping zero node expressions cached, e.g. as down values of zeroNode symbol. When zero is added to cache tree, we can test whether containing it node is of our special form, if so we can replace it with cached version.

zeroNode // ClearAll
zeroNode[1, _] = 0;
zeroNode[2, i_] := zeroNode[2, i] = 0 @@ ConstantArray[0, i];
zeroNode[depth_, i_] := zeroNode[depth, i] = Prepend[zeroNode[depth - 1, i], zeroNode[depth - 1, i]]

integerTreeOptimizeZeroNode = Function[{tree, path},
  Module[{newPath = Most@path, node, cached},
    node = Extract[tree, newPath];
    cached = zeroNode[Depth@node, Count[node, 0]];
    While[node === cached,
      tree[[Sequence @@ newPath]] = cached;
      newPath = Most@newPath;
      node = Extract[tree, newPath];
      cached = zeroNode[Depth@node, Count[node, 0]]
    ];
  ]
  ,
  HoldFirst
];
integerTreeGetOrSetLeaf = Function[{tree, path, value},
  Module[{val},
    val = Quiet@Check[
      Extract[tree, path]
      ,
      Fold[integerTreeResizeStep, Unevaluated@tree, path];
      -1
    ];
    If[Not@IntegerQ@val, val = Head@val];
    If[val < 0,
      val = value;
      If[IntegerQ@Extract[tree, path],
        tree[[Sequence @@ path]] = val
      (* else *),
        tree[[Sequence @@ path, 0]] = val
      ];
      If[val === 0, integerTreeOptimizeZeroNode[tree, path]]
    ];
    val
  ],
  HoldAll
];

Time and memory usage:

AppendTo[results, "Tree cache + compilation + shared nodes" -> Table[
  Internal`InheritedBlock[{zeroNode}, Module[{res},
    $cache = {};
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ]],
  {i, 40}
]] // Last
(* {{1, 0.000206, 10736}, {2, 0.000256, 14848}, {6, 0.000448, 18920}, {14, 0.000858, 23112},
    {34, 0.001798, 27304}, {68, 0.003416, 31496}, {150, 0.007841, 35688}, {296, 0.014545, 39880},
    {586, 0.019235, 44072}, {1140, 0.017669, 48264}, {2182, 0.029496, 52456}, {4130, 0.042167, 56656},
    {7678, 0.064716, 60840}, {14368, 0.098059, 65040}, {26068, 0.137533, 69224}, {48248, 0.198948, 73424},
    {86572, 0.297026, 77608}, {158146, 0.440113, 86200}, {281410, 0.645397, 97752}, {509442, 0.945092, 115080},
    {901014, 1.39239, 128512}, {1618544, 2.01232, 159560}, {2852464, 3.04968, 180984}, {5089580, 4.37024, 237376},
    {8948694, 6.2295, 263520}, {15884762, 8.86484, 367256}, {27882762, 12.9779, 413672}, {49291952, 18.4895, 610232},
    {86435358, 27.0952, 674016}, {152316976, 39.3753, 1047472}, {266907560, 57.412, 1176016}, {469232204, 81.8548, 1901088},
    {821844316, 119.4, 2092472}, {1442300988, 170.801, 3499760}, {2525295380, 246.583, 3889176}, {4426185044, 355.022, 6659784},
    {7747801190, 516.578, 7312040}, {13567867834, 731.325, 12764352}, {23745303556, 1059.77, 14108216}, {41557384062, 1592.29, 24914200}} *)

---

Iterative version

Let's gather data on a lists used after calculating f@n's for subsequent ns from 1 to nMax.

$cache = {};
$cacheHistory = Table[f@n; $cache, {n, 40}];

Set of a lists can be generated from cache element by taking Positions and deleting trailing zeros, for example 4th cache element after calculating f@n's up to 7 contains values calculated for following a lists:

Sort[Internal`DeleteTrailingZeros /@ Position[$cacheHistory[[7, 4]], _Integer]]
(* {{}, {1}, {2}, {3}, {4}, {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {3, 1},
    {1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {1, 1, 1, 1}} *)

In a lists we get from $cacheHistory we can notice that, for given nMax and n, last elements of a lists are all integers from 1 to n, and remaining elements form all compositions of all numbers from 0 to Min[n - last, nMax - n].

Let's check this for all calculated $cacheHistory elements, i.e. up to 40:

And @@ Flatten@Table[
  SameQ[
    Sort[Internal`DeleteTrailingZeros /@ Position[$cacheHistory[[nMax, n]], _Integer]],
    Table[
      Append@last /@ Join @@ Permutations /@ IntegerPartitions@totMost,
      {last, n},
      {totMost, 0, Min[n - last, nMax - n]}
    ] // Flatten[#, 2]& // Prepend@{} // Sort
  ],
  {nMax, 40},
  {n, nMax}
]
(* True *)

Proving whether above observation is true for arbitrary large ns is left as an exercise for the reader.

Assuming that it is true, we can replace our recursive function with explicit iteration in which we can sequentially pre-compute all necessary cache elements for given n.

In recursive version absence of element in cache meant that it was not yet calculated and needs to be calculated when requested. In iterative version we know (given our above assumption) that when cache element is requested it was already calculated, so we can use absence of element in cache as sign that its calculation resulted in some chosen default cache value. This way, by not storing this default value in our cache (except when it's needed to fill space up to last non-default value in a node), we can reduce cache size.

Most common value in cache is zero, so we choose it as our default.

nextNA = Hold@Compile[{{prev, _Integer, 1}},
  Module[{prevLen, nextLen, next},
    prevLen = Length@prev;
    nextLen = prevLen + prev[[prevLen - 1]] - 2;
    next = Table[1, nextLen];
    Do[next[[i]] = prev[[i]];, {i, prevLen - 3}];
    next[[prevLen - 2]] = prev[[prevLen - 2]] + 1;
    If[nextLen >= prevLen, next[[prevLen - 1]] = 1];
    next
  ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
] /.
  Part -> Compile`GetElement //. HoldPattern[Compile`GetElement@x__ = y_] :> (Part@x = y) //.
  HoldPattern[Plus][pre___, x_, HoldPattern[Times][-1, y_], post___] :> Plus[pre, Subtract[x, y], post] //
  ReleaseHold // Last;

$cache = {};

cacheResizeStep = Function[,
  With[{node = #1},
    Which[
      IntegerQ@node,
        #1 = Array[0&, #2, 1, node],
      Length@node < #2,
        #1 = Join[node, Array[0&, #2 - Length@node, 1, Head@node]]
    ];
  ];
  Unevaluated@Unevaluated@#1[[#2]]
  ,
  HoldFirst
];

cacheGet // ClearAll
cacheGet@{-1} = 0;
cacheGet@{0} = 1;
cacheGet@na_ := Quiet@Check[Replace[Extract[$cache, na], node: Except@_Integer :> Head@node], 0]

cacheSet = With[{val = Sum[cacheGet@reduce[#, k], {k, First@#}]},
  If[val =!= 0,
    Fold[cacheResizeStep, Unevaluated@$cache, #];
    $cache[[Sequence @@ #]] = val
  ]
]&;

preCompute = With[{oldN = Length@$cache},
  Do[
    If[nn > oldN, Do[cacheSet@{nn, last}, {last, nn}]];
    Do[
      Module[{na = ConstantArray[1, tot + 2]},
        na[[1]] = nn;
        Do[
          Do[
            na[[-1]] = last;
            cacheSet@na
            ,
            {last, nn - tot}
          ];
          na = nextNA@na;
          ,
          2^(tot - 1)
        ]
      ],
      {tot, Max[oldN - nn + 1, 1], Min[nn, # - nn]}
    ];
    If[nn > oldN, $cache[[nn, 0]] = Sum[cacheGet@{nn, k}, {k, nn}]]
    ,
    {nn, Ceiling[oldN, 2] / 2 + 1, #}
  ]
]&;

f // ClearAll
f@n_ := (preCompute@n; $cache[[n, 0]])

Time and memory usage:

AppendTo[results, "Tree cache + compilation + iterative" -> Table[
  Module[{res},
    $cache = {};
    Prepend[AbsoluteTiming@MaxMemoryUsed[res = f@i], res]
  ],
  {i, 40}
]] // Last
(* {{1, 0.000238, 5152}, {2, 0.000694, 5264}, {6, 0.00071, 6768}, {14, 0.001154, 6888},
    {34, 0.002287, 7136}, {68, 0.003436, 7424}, {150, 0.006044, 7808}, {296, 0.009524, 8304},
    {586, 0.014249, 8896}, {1140, 0.021613, 9792}, {2182, 0.029021, 10848}, {4130, 0.045345, 12544},
    {7678, 0.051793, 14144}, {14368, 0.055507, 17112}, {26068, 0.08087, 20016}, {48248, 0.106901, 25048},
    {86572, 0.146255, 29152}, {158146, 0.216362, 37416}, {281410, 0.320636, 44344}, {509442, 0.479902, 58144},
    {901014, 0.601251, 68120}, {1618544, 0.849296, 91216}, {2852464, 1.21726, 108184}, {5089580, 1.72727, 145896},
    {8948694, 2.46205, 169600}, {15884762, 3.51142, 228200}, {27882762, 5.0261, 267120}, {49291952, 7.33004, 361400},
    {86435358, 10.3712, 416728}, {152316976, 14.6958, 567296}, {266907560, 21.4333, 658512}, {469232204, 32.6764, 890880},
    {821844316, 44.3283, 1017496}, {1442300988, 62.5927, 1376632}, {2525295380, 89.3019, 1578752}, {4426185044, 127.182, 2138352},
    {7747801190, 183.395, 2425000}, {13567867834, 261.899, 3297264}, {23745303556, 378.116, 3757568}, {41557384062, 533.63, 5084384}} *)

---

Comparisons

Let's check that all methods gave same results

SameQ @@ results[[All, All, 1]]
(* True *)

and compare their time and memory usage

ReplacePart[First@#, 1 -> GraphicsGrid[List /@ #[[All, 1]]]] &@(
  ListLogPlot[results[[All, All, First@#]], AxesLabel -> Last@#] & /@
    {2 -> "Time [s]", 3 -> "Memory [B]"}
)

We can see that simplest DownValues memoization has highest memory usage, regardless of compilation. DownValues memoization with compilation is fastest as long as we have enough memory. Iterative tree cache has lowest memory usage and, with compiled reduce, is only slightly slower than fastest variant.

Further optimizations might require rewriting in lower level language. But since this algorithm is not using any sophisticated high level Mathematica functionality, it should be doable.