Experimenting With "Tail Recursion" Using CFThread In Lucee CFML 5.3.7.47
In a recursive algorithm, "tail recursion" is when the very last call in the recursive algorithm is the recursive call of the same function. Developers generally care about "tail recursion" because it can be optimized by the runtime / compiler (depending on your runtime / compiler). While tail recursion doesn't really have anything to do with the CFThread tag in ColdFusion, I was curious to see if a CFThread tag could "recursively" spawn itself. Historically, with Adobe ColdFusion (ACF), nested CFThread tags have been blocked. However, with Lucee CFML, you can have deeply nested CFThread tags. So, "recursing" a CFThread tag should be possible in Lucee CFML 5.3.7.47.
To test this, I created a simple demo in which we are going to sum the values from a given number down to zero. So, for example, when given the number 10, we're going to reduce this as such:
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 54
And, we're going to calculate this in such a way that each step in this reduction will take place inside a "recursively spawned" CFThread tag:
<cfscript>
reduceWithThread( 0, 10 );
echo( "Done." );
// ------------------------------------------------------------------------------- //
// ------------------------------------------------------------------------------- //
public void function reduceWithThread(
required numeric reduction,
required numeric value
) {
// NOTE: CFThreads have to be UNIQUE per request. As such, we have to include a
// unique identifier in the thread name since we're calling it "recursively"
// within a single request.
thread
name = "tailRecursion.#createUniqueId()#"
reduction = reduction
value = value
priority = "low"
{
systemOutput( "Spawning thread( #thread.name# ) for value, #value#.", true, true );
sleep( 1000 );
// BASE CASE: Only recurse down to zero, then stop calculating reduction.
if ( value <= 0 ) {
systemOutput( "REDUCTION: #reduction#.", true, true );
return;
}
// TAIL RECURSION: This isn't strictly recursion, so the concept of "tail
// recursion" requires some degree of squinting and imagination; but, when
// executing a recursive algorithm, tail recursion means that the very last
// call in the algorithm is the recursive call. And, in this case, the very
// last call in our CFThread is the subsequent spawning of the same CFThread.
reduceWithThread( ( reduction + value ), ( value - 1 ) );
}
}
</cfscript>
As you can see, we kick off the recursive algorithm with reduceWithThread(). Then, at the end of every CFThread tag body - with the exception of the base case, which ends the recursive algorithm - we turn around and call reduceWithThread() again. And, when we run this Lucee CFML code, we get the following terminal output:
As you can see, this works quite nicely - each CFThread tag body is able to "recursively" re-spawn itself by invoking the function that originally spawned itself. And, it properly stops recursing once it hits its base-case (a value of zero).
CAUTION: In Lucee CFML (at the time of this writing),
CFThreadtags are not "free". Due to some quirks in the request processing, eachCFThreadspawning incurs a sort of request-duplication cost that takes time and resources. Read more here:
- Lucee Appears To Incur Request-Cloning Overhead When Spawning CFThread Tags In Lucee CFML 5.3.3.62
- Temporary Upload Files Are Duplicated And Persisted When A Request Uses CFThread In Lucee CFML 5.3.6.61
That said, for small request, this should be inconsequential.
On its own, a recursive CFThread tag isn't all that interesting. But, I have some ideas about an algorithm that could be helped by the use of a recursive CFThread tag execution. As such, this post was just a stepping stone for subsequent exploration in Lucee CFML 5.3.7.47.
Want to use code from this post? Check out the license.
Reader Comments
@All,
After writing this, I got curious as to how this technique would interact with the
requestTimeoutsettings in theCFSettingtag:www.bennadel.com/blog/3939-recursive-nested-cfthreads-can-get-around-cfsetting-requesttimeout-in-lucee-cfml-5-3-7-47.htm
As you may know, asynchronous
CFThreadexecution has to adhere to the request timeout of the parent page. However, it looks like this doesn't refer to the algorithm - just theCFThreadtag body. Which means, if we break up our algorithm into a series of smaller threads, we can get around the request timeout.@All,
The major reason I was curious in looking at the possible "tail recursion" aspects of
CFThreadis because I was exploring the use of Java's Concurrent Queues to implement an in-memory queue for asynchronous processing:www.bennadel.com/blog/3940-using-javas-concurrent-queues-for-asynchronous-processing-in-lucee-cfml-5-3-7-47.htm
In that post, I use a background thread to consume the queue. But, due to a race-condition in thread tear-down, I needed to be able to recursively spawn a new thread from within itself in order to counteract and ege-case.