Sleep sort and TThread corner case

If you have not heard it yet – an anonymous genius from 4chan invented a sleep sort, brilliant esoteric sorting algorithm. I have written sleep sort implementation based on Delphi TThread class for rosettacode project, and started to experiment with the code. One of the working variants is:

program SleepSortDemo2;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes, SyncObjs;

type
  TSleepThread = class(TThread)
  private
    FValue: Integer;
    FLock: TCriticalSection;
  protected
    constructor Create(AValue: Integer; ALock: TCriticalSection);
    procedure Execute; override;
  end;

const
  ArrLen = 16;

var
  A: array[0..ArrLen - 1] of Integer;
  Threads: array[0..ArrLen - 1] of TThread;
  Lock: TCriticalSection;
  I: Integer;

constructor TSleepThread.Create(AValue: Integer; ALock: TCriticalSection);
begin
  FValue:= AValue;
  FLock:= ALock;
  inherited Create(False);
end;

procedure TSleepThread.Execute;
begin
  Sleep(1000 * FValue);
  FLock.Acquire;
  Write(FValue:3);
  FLock.Release;
end;

begin
  for I:= 0 to ArrLen - 1 do begin
    A[I]:= Random(15);
    Write(A[I]:3);
  end;
  Writeln;

  Lock:= TCriticalSection.Create;
  for I:= 0 to ArrLen - 1 do
    Threads[I]:= TSleepThread.Create(A[I], Lock);
  for I:= 0 to ArrLen - 1 do begin
    Threads[I].WaitFor;
    Threads[I].Free;
  end;
  Lock.Free;

  Writeln;
  Readln;
end.

Now, if you look at TThread source code you can see that TThread.WaitFor is called from TThread.Destroy, so it seems that there is no need for a separate  Threads[I].WaitFor call and the line #53 can be commented. Try it, and the code does not work anymore (at least it does not work on the system I used for testing – Windows 7 SP1, Celeron 530 CPU, 2 Gb RAM).

After pondering at the problem for some time I understood that TThread.Destroy just does not wait for the thread to terminate. But why? Look at the code snippet from TThread.Destroy:

  if (FThreadID <> 0) and not FFinished and not FExternalThread then
  begin
    Terminate;
    if FCreateSuspended then
      Resume;
    WaitFor;
  end;

All conditions are satisfied. You can set a breakpoint on WaitFor line and see that WaitFor method is actually called…

The answer was found in the ThreadProc function. Here is a code snippet from it:

  ..
  try
    if not Thread.Terminated then
    try
      Thread.Execute;
    except
      Thread.FFatalException := AcquireExceptionObject;
    end;
  finally
  ..

See what happens? TThread.Destroy calls Terminate and sets TThread.Terminated flag. But the thread has not started yet. Now the thread starts, ThreadProc function checks TThread.Terminated flag, and the Execute method is never called!

Advertisements

10 thoughts on “Sleep sort and TThread corner case

    • Thank you, yes, that is it. If EMB is not about to fix the problem, the problem should be documented – in some cases you should not call TThread.Terminate before TThread.WaitFor

    • I’m probably missing something, but how can that be ‘as designed’ given the implementation of TThread.Destroy? To me, it looks less like ‘bad design’ than the fact two independently-produced fixes/clean-ups to TThread were done at one point that actually conflict with each other. Obviously, if I’m picking an argument, it’s with the person who updated QC, but still…

  1. BTW, just because of this problem OTL implements ‘must execute’ policy for tasks. You can still get the Delphi behaviour by calling IOmniTaskControl.Enforce(false).

    • I thought about adding one more property to TThread – EnforceExecute, so that the fragment of ThreadProc function looks like

          if not Thread.Terminated or Thread.EnforceExecute then
          try
            Thread.Execute;
          except
            Thread.FFatalException := AcquireExceptionObject;
          end;
      
  2. Pingback: TThread Facts « The Programming Works

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s