Why is FreeQ so much faster for some specific variable names?

Question

It seems that performance of FreeQ depends on the names of symbols which appear in its arguments.

Here is an example of two large expressions which do not contain symbol b:

listac = RandomChoice[{a, c}, 1000000];
listat = RandomChoice[{a, t}, 1000000];

Applying FreeQ to these expressions results in very different timings:

RepeatedTiming[FreeQ[listac, b]]
RepeatedTiming[FreeQ[listat, b]]

{5.*10^-7, True}

{0.019, True}

Why can FreeQ instantly identify that listac doesn't contain b, but needs time to check listat?

Are there any recommendations on how to choose symbol names for best performance?

Answer 1

TLDR:

If you run into performance issues related to symbol names, rename your symbols such that System`Private`GetContentCode returns different values for each symbol you use.

Details:

I guess that the irregular performance of FreeQ is related to the indexing method used by Mathematica to speed-up pattern matching and evaluation. By indexing I mean creating an auxiliary data structure (index) which is stored alongside every expression and contains some information about the contents of the expression. Index is recalculated when expression is being constructed or updated.

Hypothetically, if one doesn't implement any indexing at all, the operations like FreeQ would always require to traverse the whole expression (what takes O(n) time). This will be far from optimal.

Another hypothetical extreme case would be to store a complete list of contained symbols alongside every expression. Such index will allow one to perform all FreeQ calls in O(1) time, but there will be serious practical disadvantages: such indexes will have variable size and will be hard to process and update.

Instead of keeping a complete list of symbols, one can store, for example, an array of bits, where the first bit indicates whether expression contains any symbols starting with letter "a", the second bit indicates if there are symbols starting with "b" and so on... Such bit array can be designed to have a fixed size (e.g. 32 or 64 bit) and it will be quick to process and update via standard bitwise operations.

Such indexing method is known as bitmap indexing with binning and is common in database management software. (See https://en.wikipedia.org/wiki/Bitmap_index)

In the example above, binning is performed by a function which maps arbitrary set of symbols (data structure with infinite cardinality) into a fixed-size bit array.

An inherent feature of bitmap indexes with binning is their irregular performance. To explain this irregular performance let's consider a hypothetical FreeQ function which relies on the alphabetical bitmap index described above. If a large expression expr contains only symbols a1 and b1, then the corresponding index will indicate that this expression contains only symbols starting with "a" and with "b". If we now evaluate FreeQ[expr, c1], our hypothetical FreeQ function can instantly (in O(1) time) return True because index of expr indicates that there are no symbols starting with "c". However if we evaluate FreeQ[expr, a2], then our hypothetical FreeQ function will be unable to return a result based on the information in index. While the index shows that there are symbols starting with "a", it is not clear if specifically a2 is a member of expr. Thus, our FreeQ function will have to traverse the expression and will take O(n) time.

In practice it may not be the best choice to use the first letter of the symbol name for indexing purposes. For example, a user may decide to start all variable names with the same letter (e.g. x1,x2,x3,...). In this case the performance of functions which rely on indexing may be reduced. Instead of the first letter of the symbol name, one can use, for example, the first letter (or first several bits) of some hash of the symbol name. In this case even symbols with very similar (but not identical) names will likely set different bits in the index and FreeQ will resort to traversing expressions more rarely. However there still will be collisions when hashed and binned names of two different symbols set the same bit in the index. I think that these type of collisions are responsible for the FreeQ irregular performance observed in the original question.

Based on developers' answers on this site, I assume that implementation of hashing/binning functions is proprietary information of WRI and they cannot share it. Luckily we don't need implementation details to resolve performance issues from the original question. We just need a way to check that binned indexes of symbols we use do not collide.

Mathematica has two undocumented functions with relevant names: System`Private`GetContentCode and System`Private`CouldContainQ. I guess that GetContentCode returns binned index for given expression and CouldContainQ performs O(1) check using this index. (Note that these functions have HoldAllComplete attribute and will not evaluate their arguments. That is why I use Map in the examples below.)

Here are the results of GetContentCode for several symbols (results are shown in base 2 for readability):

Map[BaseForm[System`Private`GetContentCode[#], 2] &, {a, b, c, d, t, u, v, List}]

{$10000000000000000_2$, $1000000000000_2$, $1000000000_2$, $100_2$, $1000000000000_2$, $1000000000000_2$, $1000000000000_2$, $100000000000000000000000000000_2$}

Note that the ContentCodes for symbols named b, t, u, and v are exactly the same. These are the symbol names which cause O(n) performance of FreeQ when used together.

Next, let's consider the results of GetContentCode for expressions listac and listat defined in the original question:

Map[BaseForm[System`Private`GetContentCode[#], 2] &, {listac, listat}]

{$100000000000010000001000000000_2$, $100000000000010001000000000000_2$}

If we interpret these ContentCodes as binned indexes we can instantly deduce which symbols may be contained in the corresponding expressions and which are definitely not there. For example, the ContentCode of symbol d is $100_2$ (i.e. third bit is set). The ContentCodes of both listac and listat do not have third bit set, which means that these expressions definitely don't contain symbol d. The function System`Private`CouldContainQ gives the result consistent with this interpretation:

Map[System`Private`CouldContainQ[#, d] &, {listac, listat}]

{False, False}

If we do a similar check for symbol b we get

Map[System`Private`CouldContainQ[#, b]&, {listac, listat}]

{False, True}

which means that based on the information from index we can identify that listac can't contain symbol b. Expression listat could possibly contain b and we need to perform a full check to know for sure.

It is now not surprising that

System`Private`CouldContainQ[t, b]

returns True.

Summary:

Irregular performance of the FreeQ function in the original question is most likely related to some sort of binned bitmap indexing mechanism which Mathematica uses to speed-up evaluations. In majority of practical cases this mechanism allows FreeQ to reach O(1) performance instead of O(n). In some rare cases, collisions of binned indexes will reduce performance to to original O(n). If such collisions give noticeable increase of calculation time it may be helpful to rename used symbols such that their binned indexes do not collide. One can use System`Private`GetContentCode function to get the value of binned index for any given symbol name.