Welcome to the Lounge

be fit - and agile   BEFITANDAGILE
perhaps?             (anag)

OriginalGriff wrote:

INDEFATIGABLE

Radar-boy: "Sir, I'm picking up the HMS In... In... Ind... Ind... Inde..."

*10 minutes later*

"...Inde... Indefatigable on our scanners!"

Captain: "I know, boy... it sunk us 5 minutes ago..."

honey the codewitch wrote:

Each JMP operand spawns a fiber (basically a thread).

Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.

honey the codewitch wrote:

Yes I do and the performance is god awful.

honey the codewitch wrote:

Plus each fiber only lives for the duration of one character.

Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.

Eddy Vluggen wrote:

So, light weight threads that are short-lived?

private struct _Fiber
{
	public readonly int[][] Program;
	public readonly int Index;
	public int[] Saved;
	public _Fiber(int[][] program, int index,int[] saved)
	{
		Program = program;
		Index = index;
		Saved = saved;
	}
	public _Fiber(_Fiber fiber, int index,int[] saved)
	{
		Program = fiber.Program;
		Index = index;
		Saved = saved;
	}
}

honey the codewitch wrote:

the performance is god awful

honey the codewitch wrote:

each fiber only lives for the duration of one character

NFA ran with 10 max fibers and 3.5 average char passes
NFA+DFA (optimized) ran with 6 max fibers and 2.5 average char passes
DFA ran with 2.5 max fibers and 1 average char passes
Pass #1
NFA: Lexed in 1.575287 msec
NFA+DFA (optimized): Lexed in 1.054843 msec
DFA: Lexed in 0.901254 msec
Pass #2
NFA: Lexed in 1.529819 msec
NFA+DFA (optimized): Lexed in 1.100836 msec
DFA: Lexed in 0.830835 msec
Pass #3
NFA: Lexed in 1.523334 msec
NFA+DFA (optimized): Lexed in 1.049213 msec
DFA: Lexed in 0.851737 msec
Pass #4
NFA: Lexed in 1.400265 msec
NFA+DFA (optimized): Lexed in 1.03485 msec
DFA: Lexed in 0.829009 msec

public static int Run(int[][] prog,LexContext input)
{
	input.EnsureStarted();
	int i,match=-1;
	_Fiber[] currentFibers, nextFibers, tmp;
	int currentFiberCount=0, nextFiberCount=0;
	int[] pc;
	// position in input
	int sp=0;
	// stores our captured input
	var sb = new StringBuilder(64);
	int[] saved, matched;
	saved = new int[2];
	currentFibers = new _Fiber[prog.Length];
	nextFibers = new _Fiber[prog.Length];
	_EnqueueFiber(ref currentFiberCount, ref currentFibers, new _Fiber(prog,0, saved), 0);
	matched = null;
	var cur = -1;
	if (LexContext.EndOfInput != input.Current)
	{
		var ch1 = unchecked((char)input.Current);
		if (char.IsHighSurrogate(ch1))
		{
			if (-1 == input.Advance())
				throw new ExpectingException("Expecting low surrogate in unicode stream. The input source is corrupt or not valid Unicode", input.Line, input.Column, input.Position, input.FileOrUrl);
			var ch2 = unchecked((char)input.Current);
			cur = char.ConvertToUtf32(ch1, ch2);
		}
		else
			cur = ch1;

	}
			
	while(0<currentFiberCount)
	{
		bool passed = false;
				
		for (i = 0; i < currentFiberCount; ++i)
		{
			var t = currentFibers[i];
			pc = t.Program[t.Index];
			saved = t.Saved;
			switch (pc[0])
			{
				case Compiler.Switch:
					var idx = 1;
					while(idx<pc.Length && -2<pc[idx])
					{
						if (_InRanges(pc, ref idx, cur))
						{
							while (-1!=pc[idx])
								++idx;

							++idx;
							passed = true;
							_EnqueueFiber(ref nextFiberCount, ref nextFibers, new _Fiber(t, pc[idx], saved), sp + 1);
							idx = pc.Length;
							break;
						}
						else
						{
							while (-1!=pc[idx])
								++idx;
							++idx;
						}
						++idx;
					}
					if(idx<pc.Length&&-2==pc[idx])
					{
						++idx;
						while(idx<pc.Length)
						{
							_EnqueueFiber(ref currentFiberCount, ref currentFibers, new _Fiber(t, pc[idx], saved), sp);
							++idx;
						}
					}
					break;
				case Compiler.Char:
					if (cur!= pc[1])
					{
						break;
					}
					goto case Compiler.Any;
				case Compiler.Set:
					idx = 1;
					if (!_InRanges(pc,ref idx, cur))
					{
						break;
					}
					goto case Compiler.Any;
				case Compiler.NSet:
					idx = 1;
					if (_InRanges(pc, ref idx,cur))
					{
						break;
					}
					goto case Compiler.Any;
				case Compiler.UCode:
					var str = char.ConvertFromUtf32(cur);
					if (unchecked((int)char.GetUnicodeCategory(str,0) != pc[1]))
					{
						break;
					}
					goto case Compiler.Any;
				case Compiler.NUCode:
					str = char.ConvertFromUtf32(cur);
					if (unchecked((int)char.GetUnicodeCategory(str,0)) == pc[1])
					{
						break;
					}
					goto case Compiler.Any;

				case Compiler.Any:
					if (LexContext.EndOfInput==input.Current)
					{
						break;
					}
					passed = true;
					_EnqueueFiber(ref nextFiberCount, ref nextFibers, new _Fiber(t, t.Index+1, saved), sp+1);

					break;
				case Compiler.Match:
					matched = saved;
					match = pc[1];
							
					// break the for loop:
					i = currentFiberCount;
					break;
							
			}
		}
		if (passed)
		{
			sb.Append(char.ConvertFromUtf32(cur));
			input.Advance();
			if (LexContext.EndOfInput != input.Current)
			{
				var ch1 = unchecked((char)input.Current);
				if (char.IsHighSurrogate(ch1))
				{
					input.Advance();
					if (-1 == input.Advance())
						throw new ExpectingException("Expecting low surrogate in unicode stream. The input source is corrupt or not valid Unicode", input.Line, input.Column, input.Position, input.FileOrUrl);
					++sp;
					var ch2 = unchecked((char)input.Current);
					cur = char.ConvertToUtf32(ch1, ch2);
				}
				else
					cur = ch1;
			}
			else
				cur = -1;
			++sp;
		}
		tmp = currentFibers;
		currentFibers = nextFibers;
		nextFibers = tmp;
		currentFiberCount = nextFiberCount;
		nextFiberCount = 0;
				
	}

	if (null!=matched)
	{
		var start = matched[0];
		// this is actually the point just past the end
		// of the match, but we can treat it as the length
		var len = matched[1];
		input.CaptureBuffer.Append(sb.ToString(start, len - start));
		return match;
	};
	return -1; // error symbol
}
static void _EnqueueFiber(ref int lcount,ref _Fiber[] l, _Fiber t, int sp)
{
	// really shouldn't happen, but maybe it might
	if(l.Length<=lcount)
	{
		var newarr = new _Fiber[l.Length * 2];
		Array.Copy(l, 0, newarr, 0, l.Length);
		l = newarr;
	}
	l[lcount] = t;
	++lcount;
	var pc = t.Program[t.Index];
	switch (pc[0])
	{
		case Compiler.Jmp:
			for (var j = 1; j < pc.Length; j++)
				_EnqueueFiber(ref lcount,ref l, new _Fiber(t.Program, pc[j],t.Saved),sp);
			break;
		case Compiler.Save:
			var slot = pc[1];
			var max = slot > t.Saved.Length ? slot : t.Saved.Length;
			var saved = new int[max];
			for (var i = 0;i<t.Saved.Length;++i)
				saved[i]=t.Saved[i];
			saved[slot] = sp;
			_EnqueueFiber(ref lcount,ref l, new _Fiber(t,t.Index+1, saved), sp);
			break;
	}
}
		
private struct _Fiber
{
	public readonly int[][] Program;
	public readonly int Index;
	public int[] Saved;
	public _Fiber(int[][] program, int index,int[] saved)
	{
		Program = program;
		Index = index;
		Saved = saved;
	}
	public _Fiber(_Fiber fiber, int index,int[] saved)
	{
		Program = fiber.Program;
		Index = index;
		Saved = saved;
	}
}