April 01, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Denis Shelomovskij | On 4/1/2014 12:38 PM, Denis Shelomovskij wrote:
> I don't want to say anything with these results. I just have no idea what
> happens here and I don't want to investigate dmd's way of optimizing things now.
This is why I recommend, when going all out in optimizing, that at some point you've gotta look at the assembler output of (insert your favorite compiler).
|
April 01, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrej Mitrovic | On 4/1/2014 1:57 PM, Andrej Mitrovic wrote:
> immutable bool[256] tab2 =
> iota(0, 0x100)
> .map!(i => isIdentifierChar0(cast(ubyte)i))
> .array;
>
Yup, that works. Purty nice!
|
April 01, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrej Mitrovic | Andrej Mitrovic:
> Also (untested):
>
> immutable bool[256] tab2 =
> iota(0, 0x100)
> .map!(i => isIdentifierChar0(cast(ubyte)i))
> .array;
Eventually this should work, and avoid the nasty cast:
immutable bool[256] tab3 =
ubyte
.max
.iota!"[]"
.map!isIdentifierChar0
.array;
Bye,
bearophile
|
April 01, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Artur Skawina | Artur Skawina: > You mention AAs, so you may already realize this, but there is no > need for a mod ctor in the above example: > > immutable bool[256] tab2 = { > bool t[256]; > for (size_t u = 0; u < 0x100; ++u) > t[u] = isIdentifierChar0(cast(ubyte)u); > return t; > }(); A recent improvement in foreach loops allows to remove the cast from your code, but I have found a new compiler bug: https://d.puremagic.com/issues/show_bug.cgi?id=12504 Bye, bearophile |
April 01, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrej Mitrovic | On 4/1/2014 1:57 PM, Andrej Mitrovic wrote: > immutable bool[256] tab2 = > iota(0, 0x100) > .map!(i => isIdentifierChar0(cast(ubyte)i)) > .array; > Incorporated your idea: https://github.com/facebook/warp/pull/5/files |
April 01, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | Walter Bright:
> Incorporated your idea:
A bit of statistics. I have counted about 260 "cast(" in the whole d files (total is 7752 CLOC lines of D code, plus 1008 blank lines and 905 lines of comments. I have not counted the lines of unittests).
The files with the higher number of casts are:
macros.d, with 86 casts
constexpr.d, with 39 casts
directive.d, with 30 casts
lexer.d, with 28 casts
stringlit.d, with 18 casts
id.d, with 16 casts
context.d, with 11 casts
skip.d, with 9 casts
Bye,
bearophile
|
April 02, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | Do I see it right that it really comes down to one use of isIdentifierStart(c) in one huge switch-case? Since "warp" seems to be interested only in ASCII properties since it is processing C code, could the switch-case be optimized into a 256 entries large jump table?
If a table lookup (char->bool) is faster than multiple comparisons, why shouldn't this apply to char->address as well?
--
Marco
|
April 02, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Marco Leise | On Wednesday, 2 April 2014 at 03:47:58 UTC, Marco Leise wrote:
> Do I see it right that it really comes down to one use of
> isIdentifierStart(c) in one huge switch-case? Since "warp"
> seems to be interested only in ASCII properties since it is
> processing C code, could the switch-case be optimized into a
> 256 entries large jump table?
>
> If a table lookup (char->bool) is faster than multiple
> comparisons, why shouldn't this apply to char->address as well?
I was thinking the same, sure would be nice if computed goto:s were standardized. (as suggested by Bearophile many times)
|
April 02, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 02-Apr-2014 02:09, Walter Bright пишет: > On 4/1/2014 12:46 PM, Dmitry Olshansky wrote: >> Would strongly suggest to use 2 kinds of data - randomized and some >> text. And, >> of course, it must be loaded at run-time. > > See Vladimir's post. > Cool. All the more confidence in using multi-stage tables for Unicode stuff ;) -- Dmitry Olshansky |
April 02, 2014 Re: Table lookups - this is pretty definitive | ||||
---|---|---|---|---|
| ||||
Posted in reply to Daniel N | 02-Apr-2014 12:27, Daniel N пишет: > On Wednesday, 2 April 2014 at 03:47:58 UTC, Marco Leise wrote: >> Do I see it right that it really comes down to one use of >> isIdentifierStart(c) in one huge switch-case? Since "warp" >> seems to be interested only in ASCII properties since it is >> processing C code, could the switch-case be optimized into a >> 256 entries large jump table? >> >> If a table lookup (char->bool) is faster than multiple >> comparisons, why shouldn't this apply to char->address as well? > > I was thinking the same, sure would be nice if computed goto:s were > standardized. (as suggested by Bearophile many times) > _Explicit_ tail call (aka switch-call) would have been cleaner and more modular. It covers all relevant cases of computed-goto such as threaded-code interpreters and also recursion-heavy functional code. -- Dmitry Olshansky |
Copyright © 1999-2021 by the D Language Foundation