For algorithms that may take longer to execute than a brief pause, it is important
to change the implementation so that the user experience is never blocked and the user is aware of their progress.
The Coordination section shows how to start, stop and pause any number of non-blocking algorithms
as tasks that run concurrently with one another as well as the main thread of user
interaction. Then, the Progress section shows how to monitor and display the progress of running tasks, and the Priority section shows how to dynamically vary their execution priorities.
Coordination
Starting a non-blocking process begins the same way as for a blocking process, with
a trigger or other means of dispatching the initiating event to the XForms model. The handler
for the model event is implemented differently, though, because it must start up a
non-blocking process on a task list and request its first time slice. We begin by
adding a few more process control variables that will help control task execution,
along with a separate data instance to keep a list of running tasks:
<instance id="SVARS">
<sort xmlns="" key="" state="play" priority="4">
...
</sort>
</instance>
<instance id="TASKS">
<list xmlns=""/>
</instance>
The
list element in the
TASKS instance will receive, as a child element, a copy of the
sort element (i.e. a set of process control variables) for each sort algorithm while it
is running. Now that sorting by
num and by
name will both be able to run at the same time, the
key attribute will indicate which sort algorithm a
sort element represents. The
state attribute will help control execution of a sort algorithm. Valid states are
play (start or continue running),
pause, and
stop (interrupted or completed). The
priority attribute will be used to specify the number of milliseconds to wait before allocating
another time slice to a sort algorithm.
Starting up a non-blocking algorithm involves first pushing a copy of its process
control variables into the TASKS list and making that copy distinguishable from other sets of process control variables.
In the case of sorting, this involves setting the key attribute appropriately. Then, as with the blocking sort algorithms, we take a copy
of the unsorted items from the DATA instance. Of course, we skip these initial steps if the user activates the sorting
trigger when the sort is already in progress. One reason the user may do this is to continue
a sort that has been paused, so if that is the case, then in lieu of those initial
steps, we change the state back to play. Here's how to start up (or continue) numeric sorting:
<action ev:event="sel-sort-num">
<action if="not(instance('TASKS')/sort[@key='num'])">
<insert context="instance('TASKS')" origin="instance('SVARS')"/>
<setvalue ref="instance('TASKS')/sort[@key='']/@key">num</setvalue>
<insert context="instance('TASKS')/sort[@key='num']/items"
origin="instance('DATA')/items/item"/>
</action>
<setvalue if="instance('TASKS')/sort[@key='num']/@state = 'pause'"
ref="instance('TASKS')/sort[@key='num']/@state">play</setvalue>
...
</action>
Note that in the blocking numeric sort algorithm, XPath subexpressions that referred
to
instance('SVARS') must be changed to start with
instance('TASKS')/sort[@key='num']. The same is true for lexicographic sorting, except for using the value
'name'' for the
key attribute.
The processing performed by each time slice of the non-blocking algorithm is encoded
in a separate XForms action that is activated by a distinct event. The event name
for numeric sorting is sel-sort-num-background-task. The final step of the non-blocking algorithm's initiator action is to dispatch that
assigned event to the XForms model to initiate processing in time slices:
<action ev:event="sel-sort-num">
...
<dispatch if="instance('TASKS')/sort[@key='num']/@state = 'play'"
name="sel-sort-num-background-task" targetid="M"/>
</action>
The processing of each time slice begins with a test to ensure that the algorithm
is still in a state of play. If so, then the task performed in each time slice will, in this case, be one iteration
of the selection sort outer loop. So, instead of using a while loop that blocks processing until all selection sort iterations are done, an if attribute is used instead to test whether one iteration should be performed. Then,
after performing one iteration of the previously defined actions, a non-blocking loop is achieved by using a delayed dispatch action to reinvoke the sel-sort-num-background-task handler after a given number of milliseconds, as follows:
<action ev:event="sel-sort-num-background-task">
<action if="instance('TASKS')/sort[@key='num']/@state = 'play'">
<action if="instance('TASKS')/sort[@key='num']/items/item">
<!-- Same actions to find smallest key and move matching item(s) from unsorted list to end of sorted list -->
<!-- (except replace subexpression "instance('SVARS')" with "instance('TASKS')/sort[@key='num']" in XPaths) -->
<dispatch name="sel-sort-num-background-task" targetid="M" delay="4"/>
</action>
...
</action>
...
</action>
Once all items have been sorted, the unsorted list of items becomes empty. The blocking algorithm's while loop terminates and then execution proceeds to post-processing code that copies the
sorted list back into the DATA instance. The non-blocking algorithm requires the same post-processing, but since
it is another possible subtask after an iteration that may not be the last, the post-processing
is placed within a conditional test that the unsorted list is empty (an empty nodeset
evaluates to boolean false). By virtue of its position in the markup, the post-processing
step runs in the same time slice as the last sorting iteration. Once the post-processing
logic is performed, the algorithm is changed to the stop state. When this occurs, execution proceeds out of the play state markup, where a final action removes the algorithm's set of process control
variables from the TASKS list if the algorithm is in the stop state:
<action ev:event="sel-sort-num-background-task">
<action if="instance('TASKS')/sort[@key='num']/@state = 'play'">
...
<action if="not(instance('TASKS')/sort[@key='num']/items/item)">
<!-- Same actions to copy sorted list back to DATA instance, replacing the unsorted list -->
<!-- (except replace "instance('SVARS')" with "instance('TASKS')/sort[@key='num']" in XPaths) -->
<setvalue ref="instance('TASKS')/sort[@key='num']/@state">stop</setvalue>
</action>
</action>
<delete if="instance('TASKS')/sort[@key='num']/@state = 'stop'"
nodeset="instance('TASKS')/sort[@key='num']"/>
</action>
Now that an algorithm can be executed without blocking the main thread of user interaction,
a user can continue to enter data into input elements, view data shown by output elements, and activate trigger elements. Although this is the intended effect in general, users should be restricted
from changing content within the DATA instance's items element because the changes will be overwritten with the sort algorithm's results.
For trigger elements that let a user insert or delete an item, XForms already offers the if attribute, so insertion and deletion into the items element can be made conditional upon the TASKS list containing no sort elements. To help restrict editing content within existing item elements, XForms provides a readonly property for every node of instance data, and the value of each node's readonly property value can be declaratively controlled by an XPath expression that tests
whether there are any sort elements in the TASKS list. User interface controls bound to read-only nodes allow users to view but not edit
the bound node's content value. Moreover, nodes default to read-only if they have
a read-only ancestor. Hence, only the items element in the DATA instance must be declared to have a readonly value of true to restrict the user from editing the num, name, and phone text content within all item elements. In the following markup, the readonly property changes between true and false whenever the TASKS list changes between containing and not containing a sort element:
<bind nodeset="instance('DATA')/items"
readonly="instance('TASKS')/sort"/>
The execution of a non-blocking algorithm can be paused at any time by programmatically
taking it out of the play state without putting it in the stop state. Furthermore, the algorithm doesn't block user interface interactions, so the
form author can give the user direct control of this capability. The following markup
puts the algorithm into the pause state upon a user's activation of an XForms trigger in the user interface:
<group ref="instance('TASKS')/sort[@key='num']">
...
<trigger>
<label>Pause</label>
<setvalue ev:event="DOMActivate" if="@state = 'play'" ref="@state">pause</setvalue>
</trigger>
...
</group>
In the next time slice, the background task event handler
action performs no operations since all code in the handler is executed on the condition
of being in the
play or
stop states. This includes the fact that no further time slices are allocated since no
further delayed
dispatch actions are performed. As mentioned above, the event handler for the
sel-sort-num event can be used not only to start the sorting algorithm but also to continue it
if it is in the
pause state. In that case, the handler does not create a new set of process control variables,
but it changes the state back to
play and then requests a time slice.
A non-blocking algorithm can also be programmatically stopped at any time before completion
by changing it to the stop state. Of course, if the algorithm is paused, then a time slice must also be requested
to ensure that the stopping logic executes. Since we must test the pause state before changing to the stop state, we request the extra time slice with a delayed action so that it runs only
after the last action changes to the stop state, as follows:
<group ref="instance('TASKS')/sort[@key='num']">
...
<trigger>
<label>Stop</label>
<action ev:event="DOMActivate">
<dispatch if="@state = 'pause'" name="sel-sort-num-background-task" targetid="M" delay="1"/>
<setvalue ref="@state">stop</setvalue>
</action>
</trigger>
...
</group>
Progress
Since the user interface remains active during the execution of a non-blocking algorithm,
it is also possible to calculate and report the algorithm's progress. The progress
can be calculated and stored in an additional process control variable. For the selection
sort, a few additional attributes are also needed to help with calculating progress,
as follows:
<instance id="SVARS">
<sort xmlns="" ...>
...
<progress unsortedCount="" unsortedGauss="" totalCount="" totalGauss=""/>
</sort>
</instance>
The unsortedCount and totalCount attributes represent the number of items still to be sorted and the total number
of items being sorted. These can be calculated using declarative calculate expressions as follows:
<bind nodeset="instance('TASKS')/sort/progress/@unsortedCount"
calculate="count(../../items/item)"/>
<bind nodeset="instance('TASKS')/sort/progress/@totalCount"
calculate="../@unsortedCount + count(../../sorted/item)"/>
These values are important for tracking the progress of each sort, but using their
direct ratio to help calculate progress would be inaccurate because selection sort
processing is quadratic, not linear. Specifically, the number of steps, i.e. the work,
needed to process
n items is given by the Gaussian summation formula:
(n+1)*n/2.
The progress of an algorithm is the difference between the total work and the ratio
of the remaining work and total work. For the selection sort, the number of remaining
work steps and total work steps can be calculated by applying the Gaussian summation
formula to the values of the unsortedCount and totalCount attributes. These calculated values are stored in the unsortedGauss and totalGauss attributes. Then, the value of the progress element can be declaratively calculated as follows:
<bind nodeset="instance('TASKS')/sort/progress/@unsortedGauss"
calculate="(../@unsortedCount div 2) * (../@unsortedCount + 1)"/>
<bind nodeset="instance('TASKS')/sort/progress/@totalGauss"
calculate="(../@totalCount div 2) * (../@totalCount + 1)"/>
<bind nodeset="instance('TASKS')/sort/progress"
calculate="concat(round(100 * (1 - @unsortedGauss div @totalGauss)), '%')"/>
The declarative calculations above automatically bind to the process control variables
of all sort algorithms as their representative sort elements are added to the TASKS list. Then, they are automatically updated as implicit additions to the processing of
each time slice. Thus, the sort algorithm is transformed into a hybrid declarative/imperative
algorithm. Furthermore, since the algorithm is non-blocking, declarative user interface
bindings can automatically show the updated progress of each time slice using the
following markup:
<group ref="instance('TASKS')/sort[@key='num']">
...
<output ref="progress">
<label> Progress: </label>
</output>
</group>
When examining the progress updates on larger data sets, there can be a small lag
in updating near the beginning, and the processing seems to slow down more perceptibly
toward the end. These effects occur because of the simplicity of the method used to
divide the processing across time slices. Each time slice performs one and only one
iteration of the sort's inner loop regardless of how much or little time that may
take. In very early iterations on large data sets, the inner loop may slightly block
processing enough to perceive. The lag near the end is more noticeable because there
is so little work being done per time slice that the idle wait time between time slices
becomes a bottleneck to completion. A more balanced approach to assigning work to
time slices could help to smooth out the processing. Solving the early stage lag would
come at a cost of designing unnatural breaking points in the algorithm processing,
whereas smoothing out and optimizing the later processing seems both more pertinent
and also easier to solve with natural breaking points in the algorithm processing.
Priority
Any non-blocking XForms action script can be given a higher or lower execution priority
using a minor variation of the delayed dispatch action. In the markup for the non-blocking processes above, the request for each
new time slice was hard-coded to be delayed by 4 milliseconds using the delay attribute. Instead, the delay can be controlled with a process control variable in
instance data, such as the priority attribute of the sort element. For a number of its elements, XForms added child elements to match certain attributes so that the child element could
use a value attribute's XPath expression to dynamically obtain the value rather than using a
hard-coded attribute value. For the dispatch action, the value attribute of a delay child element can be used to obtain the delay from the priority attribute in instance data as follows:
<dispatch name="sel-sort-num-background-task" targetid="M">
<delay value="instance('TASKS')/sort[@key='num']/@priority"/>
</dispatch>
Increasing or decreasing the execution priority is then as simple as using the setvalue action to change the priority attribute value, after which the subsequent time slices will use the new value to
set the length of delay for the successor time slice. The priority can be increased
and decreased throughout the execution of the algorithm. In the following markup,
trigger elements give the end-user direct control of the execution priority:
<group ref="instance('TASKS')/sort[@key='num']">
...
<trigger>
<label>Decrease priority</label>
<setvalue ev:event="DOMActivate" ref="@priority" value=". * 2"/>
</trigger>
<trigger>
<label>Increase priority</label>
<setvalue ev:event="DOMActivate" ref="@priority" value="choose(. > 1, . div 2, .)"/>
</trigger>
...
</group>
In this markup, the execution priority level is decreased by doubling the number of
milliseconds of delay, and it is increased by halving the number of milliseconds,
down to the minimum of a 1 millisecond delay. It is instructive to run
both sort algorithms simultaneously, and then decrease the priority level of the
first sort and increase the priority level of the second sort so that it finishes
first.
