Namespace FastBWT

public class StatisticStep

Report about one iteration of one worker during sorting process.

Fields

public int ID

Worker ID. The number of workers depends on processor count.

public long Step

Step number of current iteration. The regions of indices that are distinct in less than Step bytes are already sorted

public long Big

Number of created big regions after this step. Big regions take more time to be sorted in the next iteration

public long Small

Number of created small regions after this step

public long Point

Number of sealed points after this step. These indices are totally sorted and make no impact on the next iterations

public double Duration

Time from starting the iteration to ending the jobs of this worker. If one worker needs more time than the others, they all shall wait and loose the time

Remarks

The statistic step objects let to collect some informations about sorting process:

• Duration of the whole process.
• Duration of each iteration (Max Duration in the iteration).
• Balance of job distribution (Difference of durations in the same iteration). The difference means waste of time, but this time may be used for other tasks.
• How long are common prefixes and how many they are (Number of regions in the late iterations). This makes almost no problem for exponential sorter, because the indices, that survive to late iterations, do not have a big impact during the first iterations. But for conventional sorter this means a catastrophic long sorting process.

Example

foreach(var g in BWT.Statistics.GroupBy(s=>s.Step))
{
    Console.WriteLine("Step: {0}", g.Key);
    foreach (var s in g.OrderBy(i => i.ID))
        Console.WriteLine("  Worker {0}: Big={1}\tSmall={2}\tPoints={3}\tDuration={4:N}",
                         s.ID, s.Big, s.Small, s.Point, s.Duration);
    
    Console.WriteLine("  Total: Big={0}\tSmall={1}\tPoints={2}\tDuration={3}\tMax Duration={4}", 
                         g.Sum(s => s.Big), g.Sum(s => s.Small), g.Sum(s => s.Point), 
                         g.Sum(s => s.Duration), g.Max(s => s.Duration));
}
Console.WriteLine("Total time: {0}", (EndTime - StartTime).TotalSeconds);

This code is used now in FastBWT executable to output sorting statistics.

See also

ASorter.Sort method

ASorter.GenerateVector method

ASorter class

Project FastBWT