What is the fastest way to get a list of subexpressions and their positions?

Question

I have spent quite some time trying to figure out what the fastest way is to get a list lists of all subexpressions and their positions. I have tried things with MapIndexed, which seems ideal in cases where we have an expression in which no functions with Hold-Attributes are present that we can let evaluate freely. For Held expressions, however, I found using MapIndexed complicated and I was unable to get a practical solution using this. Furthermore, I have tried things with Extract and Position.

All these things were hinted at in the comments of/answers to the positionFunction question by Mr.Wizard, which caused me to be interested in this. Because I have spent time on this and because I feel this is quite a fundamental question, I would like to get some feedback. To be fair, I am also quite glad with my own answer, as it is considerably faster than the alternatives I found (although it took me a long time), but if there are better alternatives I would be even gladder to know. Lastly, it may be nice for me to refer to this Q&A later, if I ever write a good answer to Mr.Wizards question.

The question is: What is the fastest way to get a list of lists of subexpressions and their positions, that works with held expressions?

Test expressions

Let's make a big expression to do tests with. Let

body[i_][n_] := If[n < i, head[body[i][n + 1], body[i][n + 1]], 1];
tree12 = head[body[12][1]];
tree3 = head[body[3][1]];

We have

LeafCount[tree12] == 2^12 && LeafCount[tree3] == 2^3

(True)

Answer 1

I'm not certain I understand your goals, though I too wish there were a cleaner way to do this.
I presume that you are dissatisfied with the performance of this fairly direct solution:

index[expr_] := {Extract[expr, #, HoldComplete], #} & /@ Position[expr, _]

Your own method using both Position and Level is a clever way to vectorize this as it were. I do not understand why you gave your toExprPosLists function a hold attribute at this would seem to only complicate using it. Perhaps you would find value in this:

index2[expr_, lev_ : {0, -1}] := 
 Thread[{Level[expr, lev, HoldComplete, Heads -> True], 
   HoldComplete @@ Position[expr, _, lev]}, HoldComplete]

This returns something similar to your function and it is faster:

time = Function[x, First@Timing@Do[x, {500}]/500, HoldAll];

toExprPosLists @@ {tree12} // time
index[tree12]              // time
index2[tree12]             // time

0.003432

0.005648

0.00184

Answer 2

Solutions with Inner

Here is the function I came up with

ClearAll[toExprPosLists];
SetAttributes[toExprPosLists, HoldAllComplete]
toExprPosLists[expr_] :=
 Inner @@
  Function[
    Hold@
     Evaluate[
      List,
      Unevaluated @@
       Level[Unevaluated@expr, {0, Infinity}, #, Heads -> True],
      Position[Unevaluated@expr, _],
      #
      ]
    ]@Function[Null, HoldComplete[List@##], HoldAllComplete]

We then have

head = 6;
{
   # (*timing*),
   {
    (HoldComplete @@@ #2)[[1, All]] // Length,
    Position[tree12HC, _] // Length,
    2^12 + 2^11 + 2
    } (*number of subexpressions*)
    ,
   #2[[All, ;; 5]] (*sample of subexpressions*)
   } & @@
 (toExprPosLists @@ List@tree12HC // Timing)
Clear[head]

{
0.015144, (timing)
{6146, 6146, 6146}, (number of subexpressions)

HoldComplete[{{HoldComplete, {0}}, {head, {1, 0}}, {head, {1, 1, 0}}, {head, {1, 1, 1, 0}}, {head, {1, 1, 1, 1, 0}}}] (sample of subexpressions)
}

Remarks

All the HoldComplete wrappers and the HoldAllComplete attributes serve to minimize overhead. To see what I mean, consider the difference between

head = List;
Trace[Hold @@ tree12HC, TraceOriginal -> True] // LeafCount
Clear[head]

16411

head = List;
Trace[tree12HC, TraceOriginal -> True] // LeafCount
Clear[head]

4101

I am not sure if I have succeeded in stopping all "rebuilding of expressions". But at least I have kept such considerations in mind while making the function :).

"Less convoluted"

Note that we could also have written

ClearAll[toExprPosLists3];
toExprPosLists3[expr_] :=
 Inner[
      List,
      Level[Unevaluated@expr, {0, Infinity}, HoldComplete, Heads -> True],
      HoldComplete@@Position[Unevaluated@expr, _],
      HoldComplete
    ]

But this appears to be slower. Also this does not look much more convoluted than Mr.Wizards answer, it only uses Inner instead of Thread. However, it is slower than the function I defined above. I think I understand a little bit why this function is slower, that is why I came up with the "convoluted version" in the first place :). Below is an explanation.

About the optimization

All of this has to do with the fact that it takes a bit of time to do something like HoldComplete@@expressionWithManyArguments. That is also the reason why I let the function return something of the form HoldComplete[List[___]] rather than HoldComplete[___], because it is more likely that you will need a list than something with head HoldComplete. This allows you to prevent one more List@@expressionWithManyArguments. Also in case you do var = expressionWithManyArguments and then do List@@var, you are using twice as much memory as necessary.

However, all of that optimization/"convolution" is minor compared to the difference in performance between Inner and Thread, it seems.

Showing that Inner is bad

To take this argument that Inner is worse than Thread to the extreme, let's make our own version of Inner (that will only work correctly with a very specific subset of possible arguments). We could set

myInner[head1_, exprs__, head2_] :=
 head1 @@@ Thread[{exprs}, head2]

and

ClearAll[toExprPosLists4];
SetAttributes[toExprPosLists4, HoldAllComplete]
toExprPosLists4[expr_] :=
  myInner[
        List,
        Level[Unevaluated@expr, {0, Infinity}, HoldComplete, 
   Heads -> True],
        HoldComplete @@ Position[Unevaluated@expr, _],
        HoldComplete
      ]

Which turns out to be faster, because as it turns out Inner is just not suitable for the job.

Comparison of timings

toExprPosLists @@ tree12HC // Timing // First
toExprPosLists3[tree12] // Timing // First
toExprPosLists4 @@ tree12HC // Timing // First
index2[tree12, {0, Infinity}] // Timing // First

0.015313
0.016765
0.010508
0.006448

Remarks about Mr.Wizards answer

So, Thread seems to be the best option for this (I think it is not possible to use MapThread, though maybe we can use InheritedBlock). I think there is no optimization to be done w.r.t avoiding apply, because of the stringent syntax of Thread. In my opinion, it is a bit of a shame we end up with something matching HoldComplete[___] rather than HoldComplete[{___}], but I do not see a good way around this.