02-Mar-2013 22:09, Namespace пишет:
>> No-no and no.
>>
>> Just translate list of keywords/types to a bunch of switch-cases that
>> will give you near optimal performance. Use CTFE to construct that
>> string of D code.
>> In fact I proposed to do just 2 levels of switches: first switch by
>> length then by first char.
>
> I don't understand.
> You don't mean something like:
>
> switch (value) {
> case "if": isKeyword = true; break;
> ...
>
> right?

No.
switch(value.length)
case 2:
	switch(value[0])
	{
	case 'i':
		switch(value[1]){
		case 'f':
			return value.length == 2;
		case ...
	...
	}
...
case 3:
...
}

>
>> Even simple if you don't want to go for CTFE code-generation is to
>> make plain array of array. The length of array is exactly 256 i.e.
>>
>> Even this should have decent speed:
>>
>> string[][256] keywords = [
>> null,
>> null,
>> ...
>> //at index 'i'
>> ['int', 'if', 'invariant', 'idouble', 'ifloat' ...]
>> //array of strings starting with char for each
>> ...
>> ];
>>
>> bool isKeyword(string value)
>> {
>>     string[] toSearch = keywords[value[0]];
>>     return toSearch.canFind(value);
>> }
>
> Ok I will try it. Thank you.


-- 
Dmitry Olshansky

02-Mar-2013 22:15, Dmitry Olshansky пишет:
> 02-Mar-2013 22:09, Namespace пишет:
>>> No-no and no.
>>>
>>> Just translate list of keywords/types to a bunch of switch-cases that
>>> will give you near optimal performance. Use CTFE to construct that
>>> string of D code.
>>> In fact I proposed to do just 2 levels of switches: first switch by
>>> length then by first char.
>>
>> I don't understand.
>> You don't mean something like:
>>
>> switch (value) {
>> case "if": isKeyword = true; break;
>> ...
>>
>> right?
>
> No.
> switch(value.length)
> case 2:
>      switch(value[0])
>      {
>      case 'i':
>          switch(value[1]){
>          case 'f':
>              return value.length == 2;

return true;

I edited the post to include length switch before per-char switch.

>          case ...
>      ...
>      }
> ...
> case 3:
> ...
> }
>



-- 
Dmitry Olshansky

I hope I understand you right this time:
http://dpaste.1azy.net/4c2e4428

Was this your idea?
With this I reached between 215 and 230 msecs.

02-Mar-2013 23:01, Namespace пишет:
> I hope I understand you right this time:
> http://dpaste.1azy.net/4c2e4428
>
> Was this your idea?
> With this I reached between 215 and 230 msecs.

This is a mess of conditionals is what a direct array of 256 entries would avoid:

	int idx;
	if (value[0] != '_') {
		idx = value[0] - 'a';
		if (idx == 26) return false;
	} else {
		idx = 26;
	}
	
	if (idx < 0 || idx > 26) {
		// debug writeln("kword: ", idx, ':', value[0]);
		return false;
	}
	
	if (keywords[idx] is null) return false;
	
	return keywords[idx].canFind(value);

Gaining some speed in the process. Plus another layer of array to discern keywords by length. You see why I suggested to generate the code in the first place ? ;)

BTW what's the reason to separate keywords and type keywords? They are processed the same in lexer and only parser somewhere up above knows what to do with these regardless. Just return different token values for each.

-- 
Dmitry Olshansky

On Saturday, 2 March 2013 at 11:59:39 UTC, Dmitry Olshansky wrote:
> 02-Mar-2013 15:04, David пишет:
>> Am 02.03.2013 10:33, schrieb Namespace:
>>> For one of our courses this year we have a very cool topic: Lexer and
>>> Compiler.
>>> In the past I have already tried some experiments in this direction with
>>> Romulus and Remus, but I've never measured my Lexing time.
>>> That's why I wanted to start again to write a lexer (hitherto purely for
>>> the learning effect).
>>> I looked at the code of some of the other lexers, that are also written
>>> in D, to get some inspiration from, but currently my Lexer is a little
>>> bit slow, it requires for example ~200 msecs for std.datetime.
>>> So I wanted to ask whether there are nice people who help me to improve
>>> our lexer.
>>>
>>> Code: https://github.com/Dgame/Puzzle/blob/master/lexer.d
>>>
>>> Thanks in advance. :)
>>
>> Making `types` and `keywords` an array might improve the speed a little bit:
>>
>> if (id in types) -> if (types.canFind(id))
>> (same with keywords)
>
> That would be slower as canFind is linear search.
> Simpler way is use first letter and length to select a bucket of keywords.
>
> But otherwise, yes, the first advice is never use built-in AA as these take quite some time to allocate. Plus they not that fast to lookup as they used mod-prime not mod-power-of-2 to pick a bucket.

And it doesn't even need to:
http://d.puremagic.com/issues/show_bug.cgi?id=9522

> This is a mess of conditionals is what a direct array of 256 entries would avoid:
>
> 	int idx;
> 	if (value[0] != '_') {
> 		idx = value[0] - 'a';
> 		if (idx == 26) return false;
> 	} else {
> 		idx = 26;
> 	}
> 	
> 	if (idx < 0 || idx > 26) {
> 		// debug writeln("kword: ", idx, ':', value[0]);
> 		return false;
> 	}
> 	
> 	if (keywords[idx] is null) return false;
> 	
> 	return keywords[idx].canFind(value);
>
> Gaining some speed in the process. Plus another layer of array to discern keywords by length. You see why I suggested to generate the code in the first place ? ;)
>
> BTW what's the reason to separate keywords and type keywords? They are processed the same in lexer and only parser somewhere up above knows what to do with these regardless. Just return different token values for each.

I changed it and merged them together.
Also I use now a array of 256 entities, but I must keep the check if idx is < 0, because 'D' - 'a' is negative.
And yes I see what you meant.^^

Code: http://dpaste.1azy.net/317241c0
I reach still 215 - 230 msecs.

It is sufficient if my array has only 26 units, because I check only lower cases.

03-Mar-2013 00:03, Namespace пишет:
>> This is a mess of conditionals is what a direct array of 256 entries
>> would avoid:
>>
>>     int idx;
>>     if (value[0] != '_') {
>>         idx = value[0] - 'a';
>>         if (idx == 26) return false;
>>     } else {
>>         idx = 26;
>>     }
>>
>>     if (idx < 0 || idx > 26) {
>>         // debug writeln("kword: ", idx, ':', value[0]);
>>         return false;
>>     }
>>
>>     if (keywords[idx] is null) return false;
>>
>>     return keywords[idx].canFind(value);
>>
>> Gaining some speed in the process. Plus another layer of array to
>> discern keywords by length. You see why I suggested to generate the
>> code in the first place ? ;)
>>
>> BTW what's the reason to separate keywords and type keywords? They are
>> processed the same in lexer and only parser somewhere up above knows
>> what to do with these regardless. Just return different token values
>> for each.
>
> I changed it and merged them together.
> Also I use now a array of 256 entities, but I must keep the check if idx
> is < 0, because 'D' - 'a' is negative.
> And yes I see what you meant.^^
>

Obviously, you still largely don't :)

Use the full byte to do the lookup dammit. Saving few array slots doesn't bring your speed up. Using full byte *directly* as index does speed things up because you don't have to do *any* computations and *conditionals*.

Conditionals that can easily go both ways are the worst thing performance-wise.

I don't know how to phrase that better.

> Code: http://dpaste.1azy.net/317241c0
> I reach still 215 - 230 msecs.

Use profiling to determine what takes the most of the time. If you don't like callgrind/cachegrind (I seriously don't know why not use it) try dmd's -profile.

Looking at your main code I see some spaghetti code and passing index by pointer. Don't do that - encapsulate lexing state in some kind of struct, then the index would be implicitly passed to all functions by this pointer.

It may very well be the case you are bound by some other code. In any case after some heroic efforts Dscanner lexes std.datetime in 24 msecs, and that on linux VM powered by the oldish AMD Phenom II. What kind of CPU do you use?

-- 
Dmitry Olshansky

02-Mar-2013 23:50, Zach the Mystic пишет:
> On Saturday, 2 March 2013 at 11:59:39 UTC, Dmitry Olshansky wrote:
>> 02-Mar-2013 15:04, David пишет:
>>> Am 02.03.2013 10:33, schrieb Namespace:
>>>> For one of our courses this year we have a very cool topic: Lexer and
>>>> Compiler.
>>>> In the past I have already tried some experiments in this direction
>>>> with
>>>> Romulus and Remus, but I've never measured my Lexing time.
>>>> That's why I wanted to start again to write a lexer (hitherto purely
>>>> for
>>>> the learning effect).
>>>> I looked at the code of some of the other lexers, that are also written
>>>> in D, to get some inspiration from, but currently my Lexer is a little
>>>> bit slow, it requires for example ~200 msecs for std.datetime.
>>>> So I wanted to ask whether there are nice people who help me to improve
>>>> our lexer.
>>>>
>>>> Code: https://github.com/Dgame/Puzzle/blob/master/lexer.d
>>>>
>>>> Thanks in advance. :)
>>>
>>> Making `types` and `keywords` an array might improve the speed a
>>> little bit:
>>>
>>> if (id in types) -> if (types.canFind(id))
>>> (same with keywords)
>>
>> That would be slower as canFind is linear search.
>> Simpler way is use first letter and length to select a bucket of
>> keywords.
>>
>> But otherwise, yes, the first advice is never use built-in AA as these
>> take quite some time to allocate. Plus they not that fast to lookup as
>> they used mod-prime not mod-power-of-2 to pick a bucket.
>
> And it doesn't even need to:
> http://d.puremagic.com/issues/show_bug.cgi?id=9522

Yes, obviously AA is becoming a central pain point that needs fixing. If you are inclined to help I suggest you join forces with H.S. Teoh and Dicebot and help fixing the AA.

-- 
Dmitry Olshansky

I never used the -profile flag before (only -conv) so I want to ask if I understand it right:
http://dpaste.1azy.net/4382097b
It seems that the call which is listed on line 133

1589328      214949      214948           0     pure @trusted dchar std.utf.decode!(const(immutable(char)[])).decode(ref const(immutable(char)[]), ref uint)

take the most time/performance. Am I right?
And why is something decoded? Should I use dchar instead of char?

And I do not take anything that is already finished, because I want to be more familiar with the matter.
I want to see, what you have to note in order to get performance.
The 24 msecs would obviously be a dream, but I would be pleased with 50-100 msecs. :D