Re: Proposal for SentinelInputRange

[Jacob Carlborg]

On 2013-03-01 00:23, Walter Bright wrote:


Hmm, I hadn't thought of that. Some checking shows that VC and DMC do
not do it, gcc and clang do.


Time for some new optimizations for DMC :)

--
/Jacob Carlborg

Re: Proposal for SentinelInputRange

[Jacob Carlborg]

On 2013-03-01 07:12, Dmitry Olshansky wrote:


A 0 or a 0x1A is the end of valid D source. Period.


So I thought.

Well, I can't see the difference between 2 sentinel values: both 0 and
0x1A has to both work. For me that means both values have to be accepted
as sentinels I'd call that a tuple of sentinels.


I think I understand how Walter things here. The D code always ends with 
'0' or '0x1A'. Regardless of what the end character is, DMD will always 
add an '0' to the end.


But you do need to check for both 0 and 0x1A.

--
/Jacob Carlborg

Re: Proposal for SentinelInputRange

[Jacob Carlborg]

On 2013-02-28 17:31, Walter Bright wrote:


I don't know what you mean.


I'm just saying that you and the spec disagree. At least that's how I 
read the spec.


--
/Jacob Carlborg

Re: Migrating dmd to D?

[Jacob Carlborg]

On 2013-02-28 20:28, Arlen wrote:


Having ported Boost.units to D, I can attest to this being a lot of
work.  I did try translating first and then refactoring the code, but
that did not go well, mainly because of all the tricks and hacks
employed when doing template meta-programming in C++ that did not
translate well at all to D.  With my first attempt I pretty much ended
up with C++ code that was written in D, and that's not what I wanted.
So I had to start over, refactoring and writing D code in D as I went.
The problem with refactoring is that once you refactor a piece, chances
are that you will need to refactor everything that depends on the code
that was refactored, and that starts a domino effect.


That sounds more like one needs to figure out the intent of the code and 
not just look at the exact syntax. An easy example. C++ supports 
multiple inheritance, D does not. Trying to emulate that will most 
likely cause a lot of problem. But the use case in C++ could just be 
interfaces.


--
/Jacob Carlborg

Re: Proposal for SentinelInputRange

[Marco Leise]

Am Thu, 28 Feb 2013 14:27:28 -0800
schrieb Walter Bright :

> Two corporate users of D have also told me that their motivating case to 
> adopt D 
> was - compile speed!

That's what I thought and why I keep telling that Carthago has
to..., I mean that Phobos and the GC is not the ultimate
performance platform. You just don't get fast + safe +
convenient in one package, it's a compromise.

> Throwing compile speed under the bus is what other compiler vendors do, and 
> we're not going to do that.

I certainly hope so :D. It's just amazing that you barely
notice a delay when compiling a medium sized program. DMD
practically competes with interpreted languages here in terms
of turn-around time.

-- 
Marco

Re: Migrating dmd to D?

[Jacob Carlborg]

On 2013-02-28 16:53, Iain Buclaw wrote:


So, feel free to send me a list of questions you want me to answer. :o)


Could the GDC front end remain in C++ and changes be folded in anyway? 
These changes do not need to be direct translation of the D code.


--
/Jacob Carlborg

Re: Migrating dmd to D?

[Jacob Carlborg]

On 2013-02-28 18:18, Iain Buclaw wrote:


We still do not know what portions of the frontend is being ported over
to D.  The way gdc is written, it takes the D Frontend, removes all C++
parts that interface with dmd's backend - toElem; toIR; toObjFile;
toSymbol; toCtype; toDt (this latter one I am in the middle of removing
from gdc) and implements them to instead build GCC trees, the code
itself also being in C++.

These are all methods defined in D Front-End, and rely on calling and
interfacing with the gcc backend.  Re-writing these in D is not an
option, as require access to GCC macros.


If you're removing these functions does it matter which language they're 
written in ?


--
/Jacob Carlborg

Re: Why ranges don't return vectors?

[Marco Leise]

Am Fri, 01 Mar 2013 02:02:16 +0100
schrieb Piotr Szturmaj :

> Anytime you read one byte from typical hard disk, system reads full 
> sector - typically 512 bytes, no more, no less.

Side note: HDD manufacturers recently switched to 4 KiB
sectors (8x size). Everyone who bypasses operating system
buffers to do raw disk access now needs to query the
system for optimal buffer alignment.

-- 
Marco

Re: Unittests and assert

[Jacob Carlborg]

On 2013-02-28 16:39, Andrei Alexandrescu wrote:


http://www.linfo.org/rule_of_silence.html


Well I see. But rspec isn't just for running tests and displaying if 
they passed or not. You can use it to generate a form of specification 
for your application.


--
/Jacob Carlborg

Re: Migrating dmd to D?

[Rob T]

On Thursday, 28 February 2013 at 07:34:11 UTC, Jacob Carlborg 
wrote:

[...]

Long term goal:

When the translation is done we should refactor the 
compiler/front end to be a library, usable by other tools.




Yes that would be awesome. It can make the exact same tool at 
least 10x more useful and versatile.


I'm a big fan of tools that allow plugins, so I would also like 
to see parts of the compiler be written as loadable plugins that 
can be swapped in/out with different versions, and also to allow 
the tool set to be extensible by anyone.


--rt

Re: Proposal for SentinelInputRange

[Chris Nicholson-Sauls]

On Friday, 1 March 2013 at 06:33:42 UTC, deadalnix wrote:


struct GenericSentinelRange(R, Sentinel) {
R r;

@property auto front() {
return r.front;
}

void popFront() {
r.popFront();
}

@property empty() {
return r.front == Sentinel;
}
}


That's exactly what I wrote as well, when I played with the idea 
before posting.  Except I just called the sentinel constant S and 
added 'enum sentinel = S;' -- not significant extra work.


We don't need a new type of range at all. You confuse 
legitimate uses case for using a sentinel to terminate a range 
and uses case where an actual sentinel range is needed.


I'm not confused. The use case for a sentinel range /type/ is 
always going to be the same, and singular: automating legitimate 
use cases for sentinels.  So, in effect, an argument for one is 
as good as for the other, when I'm only responding to the calls 
for use case examples. My mistake was in not making it clear that 
I was responding just to those, sorry.


You can live without, and guess what : if you use LDC (and 
probably GDC) you'll get the performance boost Walter is 
talking about.


Which presupposes that I *can* use LDC (or GDC). For many people, 
it may not be an option.  And last time I tried (which has been 
months now, admittedly) I couldn't get LDC to work for me at all, 
which is a shame since I'm actually very much interested in it.  
Either way, reliance on implementation details is not a good 
thing.

Re: Migrating dmd to D?

[Zach the Mystic]

On Thursday, 28 February 2013 at 05:32:37 UTC, Walter Bright 
wrote:

On 2/27/2013 8:03 PM, Marco Leise wrote:

There are > 1000 open bugs and well known, expected language
features not implemented. In my opinion, the compiler should
be ported after all important language features are finalized.
I don't mean syntax, but stuff that only bearophile has the
complete list of: shared, allocators, ...
Also DMD leaks memory -> it is tempting to use the GC -> DMD
will often be a whole lot slower in the end. :D
Also Phobos is designed for safety and generic programming,
not for raw speed like many old C functions (at least that's
my experience). E.g. I have seen or written Unicode and
float/string conversion routines that perform 7x to 13x faster
than the 'obvious' way in D.



The motivation for the migration is not for fun, it's not even 
to "eat our own dogfood". The idea is to make the front end 
more reliable and more flexible by using D features that help. 
This should make us more productive and able to fix problems 
faster and presumably have fewer problems in the first place.


There are a long list of D things that will help.


So you're saying some of our dogfood is actually caviar then...

I would divide the caviar into two groups, manifest and hidden. 
The manifest caviar is the easiest to sell. Hidden caviar is the 
benefits which are unexpected by at least a portion of the D 
community. Each piece of hidden caviar therefore needs one or 
more champions.


Not that this is a perfect example, but the lexer being assembled 
by Brian and Dmitri seems to have a spark of the hidden caviar 
about it, lending weight to the "clean room" camp. The politics 
of "existing" versus "clean room" must be mastered because 
there's a lot of room for resentment there if the wrong choices 
are made, it seems to me.


One thing both "clean room" and "existing" have, or should have, 
in common is the test suite, which is probably a better spec than 
the spec is. Perhaps a method can be devised which makes it easy 
to divide and conquer the test suite.

Re: Migrating dmd to D?

[Philippe Sigaud]

>> (* Knowing the guts of a front end means you can decide to add type
>> system and syntax extensions for private use. :P)
>
> Ah, I see where the wind blows ;)

Or, even better, an extensible FE with commonly distributed extensions
like the Haskell compiler. And, of course, an AST macro system and a
pony ;)

No, scratch that, with a good macro system, we can have the pony.

Re: Migrating dmd to D?

[Marco Leise]

Am Thu, 28 Feb 2013 18:44:31 +0100
schrieb Timon Gehr :

> * wc -l reveals that the DMD front end source code is roughly 30 to 40 
> times larger than it should be for what it does in my opinion.

That can only mean that you don't really know what it does in
my opinion. Sure such a large code base accumulates duplicates
since not everybody knows about all helper functions or copy
and paste was the least intrusive bug fix somewhere, but you
don't really believe that 94% of the front end are
unnecessary, do you?

> (* Knowing the guts of a front end means you can decide to add type 
> system and syntax extensions for private use. :P)

Ah, I see where the wind blows ;)

-- 
Marco

Re: Proposal for SentinelInputRange

[deadalnix]

On Friday, 1 March 2013 at 06:19:19 UTC, Chris Nicholson-Sauls 
wrote:
A use case that comes immediately to mind: a sentinal range 
that, yes wraps, an infinite (but predictable!) range, 
effectively allowing you to take a head-slice of the infinite 
range.


auto foo = infiniteRangeOfEvenNumbers();
auto upto1000 = GenericSentinalInputRange!1000( foo );



struct GenericSentinelRange(R, Sentinel) {
R r;

@property auto front() {
return r.front;
}

void popFront() {
r.popFront();
}

@property empty() {
return r.front == Sentinel;
}
}

We don't need a new type of range at all. You confuse legitimate 
uses case for using a sentinel to terminate a range and uses case 
where an actual sentinel range is needed.


So... I could live without a standard sentinal range concept 
(have so far, using sentinal injection with input ranges, which 
as Walter pointed out is really an incorrect use (abuse?) of 
input ranges), but I also know I'd be using it if it existed 
(and thereby cleaning up some code versus how I do it now).


You can live without, and guess what : if you use LDC (and 
probably GDC) you'll get the performance boost Walter is talking 
about.

Re: Migrating dmd to D?

[Rob T]

On Thursday, 28 February 2013 at 17:04:24 UTC, Marco Leise wrote:

Am Wed, 27 Feb 2013 21:32:08 -0800
schrieb Walter Bright :

The motivation for the migration is not for fun, it's not even 
to "eat our own dogfood". The idea is to make the front end 
more reliable and more flexible by using D features that help. 
This should make us more productive and able to fix problems 
faster and presumably have fewer problems in the first place.


There are a long list of D things that will help.


In a way it means "eat your own dogfood" if you compare C++ to
D. C++ may be lacking, but you can emulate a few things and it
has good code analysis tools.
Maybe I'm too pessimistic in thinking this will take a year,
stop bug fixes and stall language design issues from being
resolved as well as slow the compiler down notably, since
you'll be writing easy to maintain code using Phobos and a GC
and that is always slower than ASM, right? :p


The biggest benefit I predict that will come from an effort like 
this, is the productive change that comes about when you "eat 
your own dog food".


--rt

Re: Proposal for SentinelInputRange

[Chris Nicholson-Sauls]

A use case that comes immediately to mind: a sentinal range that, 
yes wraps, an infinite (but predictable!) range, effectively 
allowing you to take a head-slice of the infinite range.


auto foo = infiniteRangeOfEvenNumbers();
auto upto1000 = GenericSentinalInputRange!1000( foo );

Yes, in this contrived example, one could use take(), but what 
about an infinite range that can be predicted to always hit 
certain points, but is not restricted to those points?



As for other cases of sentinal ranges wrapping others, in 
particular arrays, there seems to be no mention of what I expect 
would be the most common use case: wherein the code which 
instantiates the sentinal range can guarantee that the sentinal 
already exists in the source data/range, because it *put* it 
there -- the lexer remains a fine example, as it tacks the 
terminating \0 on.  There is no need for extra checks, because 
there is no need to *replace* the source data with the sentinel. 
It is naturally reduced to it through normal processing.



Other apparent use cases: list processing (Andrei has mentioned 
this already, for singly-linked lists); protocol processing with 
a terminate-transaction message, or similar; state sequences 
(which can include lexers and parsers, as it happens).  This is 
just off the top of my head.


Can we do it now, without a special type?  Yes.  Is there any 
gain from introducing the special type, versus what can be done 
now?  Yes, sometimes.  Is there any harm in introducing the 
special type?  No.  Is there significant cost in adding it?  No.  
Should this just be handled by compiler optimization?  Yes and no 
-- yes in that a great compiler should be able to optimize *many* 
(but not neccessarily all!) cases; but no in that including 
implementation details in a language spec is usually bad mojo.  
Of course, any compiler that could optimize the common cases, 
could at least as readily optimize the use of a sentinal range -- 
in fact, I'd expect it to open optimization paths for some of the 
corner cases that might otherwise not have been optimized.


So... I could live without a standard sentinal range concept 
(have so far, using sentinal injection with input ranges, which 
as Walter pointed out is really an incorrect use (abuse?) of 
input ranges), but I also know I'd be using it if it existed (and 
thereby cleaning up some code versus how I do it now).

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

01-Mar-2013 02:57, Walter Bright пишет:

On 2/28/2013 10:39 AM, Dmitry Olshansky wrote:

That would mean that when you see 0 or 0x1A you do a check to see if
that's the
end of input then decide it's really the end of input.


A 0 or a 0x1A is the end of valid D source. Period.


So I thought.

Well, I can't see the difference between 2 sentinel values: both 0 and 
0x1A has to both work. For me that means both values have to be accepted 
as sentinels I'd call that a tuple of sentinels.


> But that doesn't mean the sentinel has to be a tuple.

Should I say you are getting cryptic?

--
Dmitry Olshansky

Re: Migrating dmd to D?

[Russel Winder]

Walter,

On Thu, 2013-02-28 at 14:46 -0800, Walter Bright wrote:
[…]
> I know I probably come off as a ninny about this, but professional users will 
> run screaming from any open source code unless it contains:
> 
> 1. a copyright notice
> 2. a license
> 3. who owns the above

Not ninni-ish at all, very sensible. Of course it is not the
professional users that worry about these things, it is their lawyers.
Worse there is a whole collection of misunderstanding and
misapprehensions, not to mention FUD, about the various well known
licences.

-- 
Russel.
=
Dr Russel Winder  t: +44 20 7585 2200   voip: sip:russel.win...@ekiga.net
41 Buckmaster Roadm: +44 7770 465 077   xmpp: rus...@winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder


signature.asc
Description: This is a digitally signed message part

Re: Why ranges don't return vectors?

[Brad Anderson]

On Friday, 1 March 2013 at 03:44:30 UTC, H. S. Teoh wrote:


You can make a buffered range that reads in a large chunk of 
data at a
time, and .front and .popFront merely move an internal pointer 
until it
reaches the end of the buffer, then the next buffer page is 
loaded in.
In this case, .front is very simple (just a pointer lookup) and 
will

probably be inlined by an optimizing compiler.

Just because the abstraction is reading per-element, doesn't 
mean the

implementation has to literally do that!


T


Isn't this essentially what is going on in stdio when a range 
uses fread?

Re: Why ranges don't return vectors?

[H. S. Teoh]

On Fri, Mar 01, 2013 at 03:35:23AM +0100, Chris Cain wrote:
> On Friday, 1 March 2013 at 01:02:17 UTC, Piotr Szturmaj wrote:
> >Seriously, nobody will ever get performance from single-element
> >iterator/range pattern - this makes CPU stall!
> 
> There's no reason you can't do that. In fact, some ranges already do
> this. Take a look at std.stdio.File.byChunk and byLine. This isn't
> appropriate for all ranges, though. Like arrays, for instance. You
> want to be able to access single elements and do things with them,
> otherwise the abstraction is pointless.

You can make a buffered range that reads in a large chunk of data at a
time, and .front and .popFront merely move an internal pointer until it
reaches the end of the buffer, then the next buffer page is loaded in.
In this case, .front is very simple (just a pointer lookup) and will
probably be inlined by an optimizing compiler.

Just because the abstraction is reading per-element, doesn't mean the
implementation has to literally do that!


T

-- 
"Maybe" is a strange word.  When mom or dad says it it means "yes", but
when my big brothers say it it means "no"! -- PJ jr.

Re: Are there any default dmd optimizations

[Walter Bright]

On 2/28/2013 10:32 AM, foobar wrote:

At a bare minimum, there should be a well defined place to notify *users* (NOT
DMD contributers) about language changes *ahead of time*. If such place is not
defined, than people do not know where to look for that info if that is even
available at all. This at least will remove the element of surprise.


The mailing lists serve that purpose, and the discussion was on the mailing list 
(which is an echo of what happens on github). It also showed up in the bugzilla 
n.g., as do all things posted on bugzilla.


You could argue that there's too much other 'noise' on those things. But at what 
point can one decide what is 'noise' and what isn't? Everybody has a different 
set of things they want to watch.



For D to be really open as it claims to be, there should be additional
guidelines about the decision making process itself. This should be made
accessible for *users* (D programmers). I need not be a core DMD contributer,
nor should I need to know C++ or DMD's internals, Nor should I need to browse
among hundreds of bugs on bugzilla or pull requests on github (both can be
labeled very poorly) to discern out of that sea of information what are the
*few* visible changes to the language and core library APIs.


All of the changes affects somebody, otherwise they would never have gotten onto 
bugzilla in the first place.


There are searches you can make on bugzilla for fulfilled enhancements only, 
such as:


http://d.puremagic.com/issues/buglist.cgi?chfieldto=Now&query_format=advanced&chfield=resolution&chfieldfrom=2013-02-18&chfieldvalue=FIXED&bug_severity=enhancement&bug_status=RESOLVED&version=D2&version=D1%20%26%20D2&resolution=FIXED&product=D

Re: Are there any default dmd optimizations

[Walter Bright]

On 2/28/2013 3:07 PM, Timon Gehr wrote:

On 03/01/2013 12:01 AM, Walter Bright wrote:

On 2/28/2013 11:03 AM, Timon Gehr wrote:

It's really easy. DMD can be convinced to do a sufficient[ly] conservative
analysis
even now, but the behaviour is undocumented and seems unintentional.


 void main() {
 void foo()() { bar(); }
 void bar()() { i = 3; }
 int i;
 foo();
 }


No, the compiler is not being clever here,


I wasn't stating that.


nor is this undocumented.


Where is it documented?


Under templates, it says that templates are instantiated in the scope of the 
corresponding template declaration.


At the time of foo(); bar has been added to the scope.



Obviously. In the above code all templates are instantiated. This is about which
state of the function local symbol table is used.


C++ has the notion of point of instantiation and point of definition, with D, 
it's about scope of instantiation and scope of definition instead.

Re: DIP28, on properties, availabel for destruction as well

[deadalnix]

On Thursday, 28 February 2013 at 14:55:06 UTC, angel wrote:

There _is_ reason.
You may, possibly, argue this reason is not important enough - 
here you might be right or wrong, I don't know.
The point is a @property should behave as close as possible to 
a real variable:


class A {
int field;
}
auto a = new A();
auto x = a.field = 3;

Now you 'upgrade' 'field' to a @property

class A {
int _field;
@property ??? field(int val) {
_field = val;


return _field = val;


}
}
auto a = new A();
auto x = a.field = 3;
The above line should behave _identically_ to the previous case.
Will it, if you define "@property char field(int val)" ? 
Apparently no.


The current proposal is simpler and allow more. It surely does 
allow to do crazy stupid things, but you can't really allow more 
without allowing to do dumb things.

Re: Why ranges don't return vectors?

[Chris Cain]

On Friday, 1 March 2013 at 01:02:17 UTC, Piotr Szturmaj wrote:
Seriously, nobody will ever get performance from single-element 
iterator/range pattern - this makes CPU stall!


There's no reason you can't do that. In fact, some ranges already 
do this. Take a look at std.stdio.File.byChunk and byLine. This 
isn't appropriate for all ranges, though. Like arrays, for 
instance. You want to be able to access single elements and do 
things with them, otherwise the abstraction is pointless.

Re: Why ranges don't return vectors?

[bearophile]

Piotr Szturmaj:

I know it can't be easy drop-in addition to the current range 
implementation, but who knows...


Time ago I have suggested in this newsgroup that idea, naming it 
"vectorized lazyness", that was mostly ignored:


http://web.archiveorange.com/archive/v/j3CAOE6ZVy4122g4OfhS

It's also related to the idea of Segmented Iterators that I have 
discussed later in this same newsgroup (I think I received no 
answers):


http://pdf.aminer.org/000/136/863/segmented_iterators_and_hierarchical_algorithms.pdf

I think that so far there is only a little amount of vectorized 
lazyness implemented in Phobos, search for "semi-lazy parallel 
map" here:

http://dlang.org/phobos/std_parallelism.html

Bye,
bearophile

Re: Proposal for SentinelInputRange

[deadalnix]

On Friday, 1 March 2013 at 01:46:34 UTC, Walter Bright wrote:

On 2/28/2013 5:29 PM, Andrei Alexandrescu wrote:

On 2/28/13 7:34 PM, Walter Bright wrote:

On 2/28/2013 4:07 PM, Jonathan M Davis wrote:

I just don't see how you're going to get a
performance gain from much of anything other than strings.


I gave you other examples already. We're just going around in 
circles.


We're talking about an abstraction that doesn't exist, 
exemplifying with code
that doesn't use it. No wonder there's going to be 
miscommunication. The

solution is to spin some code.


std.regexp uses sentinels in the bytecode.


I think nobody says that this technic is useless. Simply that a 
good compiler can take advantage of it without introducing an 
higher level concept of sentinel input range.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 5:00 PM, deadalnix wrote:

On Friday, 1 March 2013 at 00:34:25 UTC, Walter Bright wrote:

I just don't see how you're going to get a
performance gain from much of anything other than strings.


I gave you other examples already. We're just going around in circles.


You didn't posted a single example that wasn't optimized by LLVM.


Search for [1] in lexer.c, i.e. lookahead cases, although these are less 
important.

I admit I was surprised that LLVM did that, though the other compilers did not. 
There are some lingering issues with ordering. The sentinel is going to be the 
rare case, and you'd often want to sort the cases so that the most likely ones 
are tested first (if it doesn't all go into a jump table indexed by the value).



I do understand that some compiler may not do the optimization, but it is show
already that this is clearly possible and in fact done. That is not an
theoretical improvement.

I don't see the point in creating a new type of range simply because some
compiler don't optimize properly.


It's a good point.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 5:29 PM, Andrei Alexandrescu wrote:

On 2/28/13 7:34 PM, Walter Bright wrote:

On 2/28/2013 4:07 PM, Jonathan M Davis wrote:

I just don't see how you're going to get a
performance gain from much of anything other than strings.


I gave you other examples already. We're just going around in circles.


We're talking about an abstraction that doesn't exist, exemplifying with code
that doesn't use it. No wonder there's going to be miscommunication. The
solution is to spin some code.


std.regexp uses sentinels in the bytecode.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 4:47 PM, H. S. Teoh wrote:

On Thu, Feb 28, 2013 at 04:36:03PM -0800, Walter Bright wrote:

On 2/28/2013 3:14 PM, jerro wrote:

ldc2 -O3 -release compiles it to:


As I posted to Timon, clang (i.e. ldc2) and gcc do do this
optimization, dmc and vc do not.


Couldn't dmc be made to do this optimization?


Yes, it could.

Re: Proposal for SentinelInputRange

[Andrei Alexandrescu]

On 2/28/13 7:34 PM, Walter Bright wrote:

On 2/28/2013 4:07 PM, Jonathan M Davis wrote:

I just don't see how you're going to get a
performance gain from much of anything other than strings.


I gave you other examples already. We're just going around in circles.


We're talking about an abstraction that doesn't exist, exemplifying with 
code that doesn't use it. No wonder there's going to be 
miscommunication. The solution is to spin some code.


Andrei

Re: optional parens everywhere except last position of function chain.

[deadalnix]

On Thursday, 28 February 2013 at 22:00:22 UTC, timotheecour wrote:

spontaneously... I love it!


is there any other spontaneous feedback?


Love it as well.

Why ranges don't return vectors?

[Piotr Szturmaj]

Seriously, nobody will ever get performance from single-element 
iterator/range pattern - this makes CPU stall!


Anytime you read one byte from typical hard disk, system reads full 
sector - typically 512 bytes, no more, no less. Anytime you read one 
byte from memory, CPU loads entire cache line from RAM into the cache 
(64 bytes on all modern Intel CPU's). Why not exploit that with ranges?


Ranges could potentially return arrays in front() (or in 
frontVector/whatever), so basically they will become ranges of ranges 
where the deepest range is always RandomAccessRange. This has obvious 
performance benefits. Everyone knows that traversing memory is faster 
than iteraring by popFront(). On the other hand memory lacks the 
flexibility of ranges - so lets make a hybrid range!


Advantages:
* performance (!)
* limited lookahead/backtracking

How?

1. instruction level parallelism: CPU's can execute few instructions in 
parallel given that they operate on different data (different vector 
elements)
2. SIMD: load entire vector to SSE/AVX register then run the operation 
on all elements at once
3. use of L1 cache: traversing vector in memory is way faster that 
calling popFront() for each vector element - likely if it's inlined


Disadvantages:
* potential inconvenience

I know it can't be easy drop-in addition to the current range 
implementation, but who knows...

Re: Proposal for SentinelInputRange

[deadalnix]

On Friday, 1 March 2013 at 00:34:25 UTC, Walter Bright wrote:

I just don't see how you're going to get a
performance gain from much of anything other than strings.


I gave you other examples already. We're just going around in 
circles.


You didn't posted a single example that wasn't optimized by LLVM. 
I do understand that some compiler may not do the optimization, 
but it is show already that this is clearly possible and in fact 
done. That is not an theoretical improvement.


I don't see the point in creating a new type of range simply 
because some compiler don't optimize properly.

Re: Proposal for SentinelInputRange

[deadalnix]

On Thursday, 28 February 2013 at 23:24:01 UTC, Walter Bright 
wrote:

On 2/28/2013 2:16 PM, Timon Gehr wrote:

// expression simplification
// (eg. trivial peephole for x!=a && x==b case sufficient)


Hmm, I hadn't thought of that. Some checking shows that VC and 
DMC do not do it, gcc and clang do.


Finally we are getting somewhere.

Re: Proposal for SentinelInputRange

[H. S. Teoh]

On Thu, Feb 28, 2013 at 04:36:03PM -0800, Walter Bright wrote:
> On 2/28/2013 3:14 PM, jerro wrote:
> >ldc2 -O3 -release compiles it to:
> 
> As I posted to Timon, clang (i.e. ldc2) and gcc do do this
> optimization, dmc and vc do not.

Couldn't dmc be made to do this optimization?


T

-- 
It only takes one twig to burn down a forest.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 3:14 PM, jerro wrote:

ldc2 -O3 -release compiles it to:


As I posted to Timon, clang (i.e. ldc2) and gcc do do this optimization, dmc and 
vc do not.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 4:07 PM, Jonathan M Davis wrote:

But that's with a pointer. You see every ++ there? That would be a popFront
call, and for most ranges, that would mean checking empty internally if the
range needs to have a sentinel value on its end, because most ranges will be a
wrapper around another range, and the only way to know whether you've reached
their end (and that therefore, front now needs to be the sentinel) is to check
for empty.


It's trivial to construct a SentinelInputRange that does not do this yet is 
correct.


I just don't see how you're going to get a
performance gain from much of anything other than strings.


I gave you other examples already. We're just going around in circles.

Re: group sortedness invariance

[bearophile]

Is this ER going to somehow help?

http://d.puremagic.com/issues/show_bug.cgi?id=9616

Bye,
bearophile

Re: Proposal for SentinelInputRange

[Jonathan M Davis]

On Thursday, February 28, 2013 23:32:16 FG wrote:
> On 2013-02-28 23:27, Walter Bright wrote:
> > I've spent a lot of time profiling compilers. The result is pretty obvious
> > - dmc is by far the fastest C/C++ compiler available, and dmd blows away
> > about every other language in compile speed.
> > 
> > Making this happen means you go after everything that eats time. Even a 5%
> > improvement is a big deal. All those drips and draps add up to big speed
> > increases.
> I get that, but it doesn't require introducing a new type of range.

Exactly.

- Jonathan M Davis

Re: Proposal for SentinelInputRange

[Jonathan M Davis]

On Thursday, February 28, 2013 13:42:34 Walter Bright wrote:
> On 2/28/2013 10:52 AM, Jonathan M Davis wrote:
> > Notice that it has to check for empty every time that the front is popped,
> > and it can't avoid that,
> 
> Yes it can avoid it - that is the whole point. Notice there are no checks
> for the sentinel here - but the code is correct:
> 
> case '>':
> p++;
> if (*p == '=')
> { p++;
> t->value = TOKge; // >=
> }
> else if (*p == '>')
> { p++;
> if (*p == '=')
> { p++;
> t->value = TOKshrass; // >>=
> }
> else if (*p == '>')
> { p++;
> if (*p == '=')
> { p++;
> t->value = TOKushrass; // >>>=
> }
> else
> t->value = TOKushr; // >>>
> }
> else
> t->value = TOKshr; // >>
> }
> else
> t->value = TOKgt; // >
> return;

But that's with a pointer. You see every ++ there? That would be a popFront 
call, and for most ranges, that would mean checking empty internally if the 
range needs to have a sentinel value on its end, because most ranges will be a 
wrapper around another range, and the only way to know whether you've reached 
their end (and that therefore, front now needs to be the sentinel) is to check 
for empty. If a range isn't a wrapper around another range, then it's probably 
an array, but arrays won't work with the sentinel range scheme, because they 
won't pass isSentinelRange. So, they'll still need a wrapper which allows them 
to be treated as a sentinel range. And so the pretty much the only case where 
you get any performance gain is with strings wrapped in a sentinel range, and 
if that's the case, I'd just special case them to use sentinels and avoid the 
sentinel range concept entirely. I just don't see how you're going to get a 
performance gain from much of anything other than strings.

For the lexer I'm working on, I just use string mixins for any operation which 
might differ between range types (e.g. strings can't use front or they'll 
decode, whereas with a range of code units, you need to use front). So, 
instead of p++ like above, I might have something like

mixin(popCodeUnit!R());

But if you're dealing with strings, and you want your function to operate on 
ranges of code units, then you're pretty much stuck either casting the strings 
to arrays of ubyte to operate on them, wrapping them in another range, or 
special casing them. And wrapping them (like your solution would require) is 
arguably the worst, because you lose out on any possibility of any helper 
functions you use optimizing for your strings, unless you write all of them 
yourself, because they won't be recognized as strings - and that includes 
functions like std.utf.decode, which any unicode-aware lexer will have to use 
at least some of the time.

- Jonathan M Davis

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 2:16 PM, Timon Gehr wrote:

 // expression simplification
 // (eg. trivial peephole for x!=a && x==b case sufficient)


Hmm, I hadn't thought of that. Some checking shows that VC and DMC do not do it, 
gcc and clang do.

Re: Proposal for SentinelInputRange

[jerro]

I didn't say can't, I said didn't. llvm handles that case 
(which does surprise me), dmc, gcc, and vc do not. Furthermore, 
I'll say "cannot" on this:


case '|':
p++;
if (*p == '=')
{   p++;
t->value = TOKorass;
}
else if (*p == '|')
{   p++;
t->value = TOKoror;
}
else
t->value = TOKor;
return;


This code is correct without assuming that r is a sentinel range, 
and it is pretty close to your code above:


void foo(R)(ref R r, ref int tvalue)
{
if(!r.empty)
switch(r.front)
{
case '|':
r.popFront();
if (!r.empty && r.front == '=')
{   r.popFront();
tvalue = 1;
}
else if (!r.empty && r.front == '|')
{   r.popFront();
tvalue = 2;
}
else
tvalue = 3;
return;
default:
}
}

If I add this:

struct R
{
ubyte* p;
@property front(){ return *p; }
@property empty(){ return *p == 0; }
void popFront() { p++; }
}

alias foo!R bar;

ldc2 -O3 -release compiles it to:

   0:  mov(%rsi),%rax
   3:  cmpb   $0x7c,(%rax)
   6:  jne3e
   8:  lea0x1(%rax),%rcx
   c:  mov%rcx,(%rsi)
   f:  mov0x1(%rax),%cl
  12:  cmp$0x7c,%cl
  15:  jne25
  17:  add$0x2,%rax
  1b:  mov%rax,(%rsi)
  1e:  movl   $0x2,(%rdi)
  24:  retq
  25:  cmp$0x3d,%cl
  28:  jne38
  2a:  add$0x2,%rax
  2e:  mov%rax,(%rsi)
  31:  movl   $0x1,(%rdi)
  37:  retq
  38:  movl   $0x3,(%rdi)
  3e:  retq

Re: Are there any default dmd optimizations

[Timon Gehr]

On 03/01/2013 12:01 AM, Walter Bright wrote:

On 2/28/2013 11:03 AM, Timon Gehr wrote:

It's really easy. DMD can be convinced to do a sufficient[ly] conservative
analysis
even now, but the behaviour is undocumented and seems unintentional.


 void main() {
 void foo()() { bar(); }
 void bar()() { i = 3; }
 int i;
 foo();
 }


No, the compiler is not being clever here,


I wasn't stating that.


nor is this undocumented.


Where is it documented?


Templates are not semantically analyzed until they are instantiated.  In
fact, they can't be semantically analyzed until they are instantiated.



Obviously. In the above code all templates are instantiated. This is 
about which state of the function local symbol table is used.

Re: Are there any default dmd optimizations

[Walter Bright]

On 2/28/2013 11:03 AM, Timon Gehr wrote:

It's really easy. DMD can be convinced to do a sufficient conservative analysis
even now, but the behaviour is undocumented and seems unintentional.


 void main() {
 void foo()() { bar(); }
 void bar()() { i = 3; }
 int i;
 foo();
 }


No, the compiler is not being clever here, nor is this undocumented. Templates 
are not semantically analyzed until they are instantiated. In fact, they can't 
be semantically analyzed until they are instantiated.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 10:39 AM, Dmitry Olshansky wrote:

That would mean that when you see 0 or 0x1A you do a check to see if that's the
end of input then decide it's really the end of input.


A 0 or a 0x1A is the end of valid D source. Period.

But that doesn't mean the sentinel has to be a tuple.

Re: Migrating dmd to D?

[Walter Bright]

On 2/28/2013 7:53 AM, Iain Buclaw wrote:

So, feel free to send me a list of questions you want me to answer. :o)


Would it impair having it accepted as part of gcc?

Re: Proposal for SentinelInputRange

[Timon Gehr]

On 02/28/2013 11:17 PM, Walter Bright wrote:

On 2/28/2013 10:12 AM, deadalnix wrote:

On Thursday, 28 February 2013 at 17:00:51 UTC, Walter Bright wrote:

On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:

If this doesn't translate to the same code, I don't know why not.


Try it and see with your favorite C compiler.

Then try the lookahead cases I also posted.


You are being stubborn here.

You claim that this is significantly faster, but give no numbers.
You claim that the compiler can't do some optimization, when LLVM does
it already.


I didn't say can't, I said didn't. llvm handles that case (which does
surprise me), dmc, gcc, and vc do not. Furthermore, I'll say "cannot" on
this:

 case '|':
 p++;
 if (*p == '=')
 {   p++;
 t->value = TOKorass;
 }
 else if (*p == '|')
 {   p++;
 t->value = TOKoror;
 }
 else
 t->value = TOKor;
 return;


Why not? It boils down to a little CSE and a trivial implies check in an 
and expression.

Re: Migrating dmd to D?

[Walter Bright]

On 2/28/2013 5:15 AM, Jacob Carlborg wrote:

On 2013-02-28 08:48, Walter Bright wrote:


Curiously, there appears to be no copyright/license information.


Should be the same as DMD uses.


Well, it should say. In fact, with the current copyright law which specifies the 
default as "copyrighted, and no license at all" it needs to or nobody can use it.


I know I probably come off as a ninny about this, but professional users will 
run screaming from any open source code unless it contains:


1. a copyright notice
2. a license
3. who owns the above

Re: Proposal for SentinelInputRange

[FG]

On 2013-02-28 23:27, Walter Bright wrote:

I've spent a lot of time profiling compilers. The result is pretty obvious - dmc
is by far the fastest C/C++ compiler available, and dmd blows away about every
other language in compile speed.

Making this happen means you go after everything that eats time. Even a 5%
improvement is a big deal. All those drips and draps add up to big speed 
increases.


I get that, but it doesn't require introducing a new type of range.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 7:00 AM, Jacob Carlborg wrote:

You'll have to convince Walter.


I've spent a lot of time profiling compilers. The result is pretty obvious - dmc 
is by far the fastest C/C++ compiler available, and dmd blows away about every 
other language in compile speed.


Making this happen means you go after everything that eats time. Even a 5% 
improvement is a big deal. All those drips and draps add up to big speed increases.


Two corporate users of D have also told me that their motivating case to adopt D 
was - compile speed!


Throwing compile speed under the bus is what other compiler vendors do, and 
we're not going to do that.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 5:02 AM, Peter Alexander wrote:

On Thursday, 28 February 2013 at 10:57:29 UTC, Walter Bright wrote:

My worry here is that we are setting a precedent for adding new range concepts.
If the only justification needed is that is saves a single operation in some
niche area of computing then we are opening the door to a LOT of different range
concepts.


There are many cases where speed is a very big deal.


Yes, are we going to add new range categories every time there's a performance
benefit to doing so?

has16ByteAlignedElements
hasUniqueElements
hasContiguousMemory
isMonotonic
isUnimodal
...
?


Depends on whether one can make a good case for them.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 10:12 AM, deadalnix wrote:

On Thursday, 28 February 2013 at 17:00:51 UTC, Walter Bright wrote:

On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:

If this doesn't translate to the same code, I don't know why not.


Try it and see with your favorite C compiler.

Then try the lookahead cases I also posted.


You are being stubborn here.

You claim that this is significantly faster, but give no numbers.
You claim that the compiler can't do some optimization, when LLVM does it 
already.


I didn't say can't, I said didn't. llvm handles that case (which does surprise 
me), dmc, gcc, and vc do not. Furthermore, I'll say "cannot" on this:


case '|':
p++;
if (*p == '=')
{   p++;
t->value = TOKorass;
}
else if (*p == '|')
{   p++;
t->value = TOKoror;
}
else
t->value = TOKor;
return;

Re: optional parens everywhere except last position of function chain.

[FG]

On 2013-02-28 23:00, timotheecour wrote:

spontaneously... I love it!


is there any other spontaneous feedback?


Spontaneously... I hate it. :)
I prefer optional parentheses everywhere.

Re: Proposal for SentinelInputRange

[Timon Gehr]

On 02/28/2013 10:40 PM, Walter Bright wrote:

On 2/28/2013 9:05 AM, deadalnix wrote:

I see nothing that can't be done by an optimizing compiler. Maybe
something is,
but I can't find it. And the example you pointed me aren't.


Tell me how front() will be optimized out to this.

 case '>':
 p++;
 if (*p == '=')
 {   p++;
 t->value = TOKge;   // >=
 }
 else if (*p == '>')
 {   p++;
 if (*p == '=')
 {   p++;
 t->value = TOKshrass;   // >>=
 }
 else if (*p == '>')
 {   p++;
 if (*p == '=')
 {   p++;
 t->value = TOKushrass;  // >>>=
 }
 else
 t->value = TOKushr; // >>>
 }
 else
 t->value = TOKshr;  // >>
 }
 else
 t->value = TOKgt;   // >
 return;



I'd be surprised if DMD couldn't do it already.

assume: popFront(){ p++; }, front()=>*p, empty()=>*p=='\0'

case '>':
popFront();
if(!empty && front == '='){
popFront();
t->value = TOKge;   // >=
}else if(!empty && front == '>'){
popFront();
if(!empty && front == '='){
popFront();
t->value = TOKshrass;   // >>=
}else if(!empty && front == '>'){
popFront();
if(!empty && front == '='){
popFront();
t->value = TOKushrass;  // >>>=
}else t->value = TOKushr;   // >>>
}else t->value = TOKshr;// >>
}else t->value = TOKgt; // >
return;

// inlining =>

case '>':
p++;
if(!(*p=='\0') && *p == '='){
p++;
t->value = TOKge;   // >=
}else if(!(*p=='\0') && *p == '>'){
p++;
if(!(*p=='\0') && *p == '='){
p++;
t->value = TOKshrass;   // >>=
}else if(!(*p=='\0') && *p == '>'){
p++;
if(!(*p=='\0') && *p == '='){
p++;
t->value = TOKushrass;  // >>>=
}else t->value = TOKushr;   // >>>
}else t->value = TOKshr;// >>
}else t->value = TOKgt; // >
return;

// expression simplification
// (eg. trivial peephole for x!=a && x==b case sufficient)
// =>

case '>':
p++;
if(*p == '='){
p++;
t->value = TOKge;   // >=
}else if(*p == '>'){
p++;
if(*p == '='){
p++;
t->value = TOKshrass;   // >>=
}else if(*p == '>'){
p++;
if(*p == '='){
p++;
t->value = TOKushrass;  // >>>=
}else t->value = TOKushr;   // >>>
}else t->value = TOKshr;// >>
}else t->value = TOKgt; // >
return;

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 9:18 AM, Steven Schveighoffer wrote:

The point is, if the lexer simply requires an input range, and not a sentinel
input range, it is more flexible for its input.  But when it does get called
with a sentinel input range, the optimizer can reap the benefits.


I suggest you compile lexer.c with various compilers, add in a !empty() call 
before every front(), and verify your assumption about this.

Re: optional parens everywhere except last position of function chain.

[timotheecour]

spontaneously... I love it!


is there any other spontaneous feedback?

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 9:25 AM, Steven Schveighoffer wrote:

On Thu, 28 Feb 2013 12:00:48 -0500, Walter Bright 
wrote:


On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:

If this doesn't translate to the same code, I don't know why not.


Try it and see with your favorite C compiler.


A sample case of 1 does not prove it's not possible, or explain why those
optimizers don't take that step.  A valid response would be to give a case why
an optimizer COULDN'T make that leap.


No, it is not. DMD is compiled with real compilers, not abstract "sufficiently 
smart compilers".



Then try the lookahead cases I also posted.


You have already stated it gets changed into a jump table.


Please, please listen to what I write. This is very frustrating. The code in 
lexer.c is there for all to see, and it amply illustrates everything I'm saying. 
For example, this code does not get translated into a jump table:


case '+':
p++;
if (*p == '=')
{   p++;
t->value = TOKaddass;
}
else if (*p == '+')
{   p++;
t->value = TOKplusplus;
}
else
t->value = TOKadd;
return;


Such an optimization
seems possible to me, even with the != 0 check outside the switch, even if not
all C compilers employ it.


It doesn't matter if it is theoretically possible if the compilers we need to 
use do not do it.

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 9:06 AM, Dmitry Olshansky wrote:

28-Feb-2013 20:56, Walter Bright пишет:

The merit is having significantly faster speed.

5% is good but doesn't count as significant. But that was for std.regex quite
sometime ago. In the lexer it might get be more.


Even 5% is worth getting, and especially so because it's low hanging fruit.

I hear from people who have switched over to D and compile speed was a BIG 
factor. And I know you are well cognizant of the fact that for regex, speed is 
also a very big deal.

Re: Migrating dmd to D?

[Iain Buclaw]

On Feb 28, 2013 9:36 PM, "pjmlp"  wrote:
>
> On Thursday, 28 February 2013 at 07:58:31 UTC, Jonathan M Davis wrote:
>>
>> On Wednesday, February 27, 2013 23:44:02 Walter Bright wrote:
>>>
>>> On 2/27/2013 9:35 PM, H. S. Teoh wrote:
>>> > How does this affect GDC/LDC? AFAIK, the GCC build scripts > do not
(yet?)
>>> > support bootstrapping D code.
>>>
>>> I don't know. I presume other gcc language tools are not written in C.
>>
>>
>> Wasn't all of that stuff written in pure C until fairly recently when
they
>> finally started letting C++ in? Maybe that was only the core stuff
though and
>> some of the language extensions aren't that strict. I don't know.
>>
>> - Jonathan M Davis
>
>
> GNAT is written in Ada.
>
> If I am not mistaken, many non standard frontends for Modula-2, Modula-3
and Pascal also use their own languages.
>
> http://gcc.gnu.org/frontends.html
>
> --
> Paulo

See my message above. The problem is not what language the frontend is
written in, the problem is not requiring to interface to the gcc backend
from the parts that are written in D.

Regards
-- 
Iain Buclaw

*(p < e ? p++ : p) = (c & 0x0f) + '0';

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 9:05 AM, deadalnix wrote:

I see nothing that can't be done by an optimizing compiler. Maybe something is,
but I can't find it. And the example you pointed me aren't.


Tell me how front() will be optimized out to this.

case '>':
p++;
if (*p == '=')
{   p++;
t->value = TOKge;   // >=
}
else if (*p == '>')
{   p++;
if (*p == '=')
{   p++;
t->value = TOKshrass;   // >>=
}
else if (*p == '>')
{   p++;
if (*p == '=')
{   p++;
t->value = TOKushrass;  // >>>=
}
else
t->value = TOKushr; // >>>
}
else
t->value = TOKshr;  // >>
}
else
t->value = TOKgt;   // >
return;

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 9:10 AM, Andrei Alexandrescu wrote:

I don't think what I said was understood.


I know the feeling :-)

Re: Proposal for SentinelInputRange

[Walter Bright]

On 2/28/2013 10:52 AM, Jonathan M Davis wrote:

Notice that it has to check for empty every time that the front is popped, and
it can't avoid that,



Yes it can avoid it - that is the whole point. Notice there are no checks for 
the sentinel here - but the code is correct:


case '>':
p++;
if (*p == '=')
{   p++;
t->value = TOKge;   // >=
}
else if (*p == '>')
{   p++;
if (*p == '=')
{   p++;
t->value = TOKshrass;   // >>=
}
else if (*p == '>')
{   p++;
if (*p == '=')
{   p++;
t->value = TOKushrass;  // >>>=
}
else
t->value = TOKushr; // >>>
}
else
t->value = TOKshr;  // >>
}
else
t->value = TOKgt;   // >
return;

Re: Migrating dmd to D?

[pjmlp]

On Thursday, 28 February 2013 at 07:58:31 UTC, Jonathan M Davis 
wrote:

On Wednesday, February 27, 2013 23:44:02 Walter Bright wrote:

On 2/27/2013 9:35 PM, H. S. Teoh wrote:
> How does this affect GDC/LDC? AFAIK, the GCC build scripts 
> do not (yet?)

> support bootstrapping D code.

I don't know. I presume other gcc language tools are not 
written in C.


Wasn't all of that stuff written in pure C until fairly 
recently when they
finally started letting C++ in? Maybe that was only the core 
stuff though and
some of the language extensions aren't that strict. I don't 
know.


- Jonathan M Davis


GNAT is written in Ada.

If I am not mistaken, many non standard frontends for Modula-2, 
Modula-3 and Pascal also use their own languages.


http://gcc.gnu.org/frontends.html

--
Paulo

Re: D as a prototyping language (for C/C++ projects)

[Jacob Carlborg]

On 2013-02-28 18:08, Andrei Alexandrescu wrote:


T tap(alias func)(T x) { func(x); return x; }

It's the kind of chaff that doesn't do any real work and only dilutes
the value of a library, but I do think a tap tapping into a range does
real work and would be a valuable addition.


What about a function allowing both?

--
/Jacob Carlborg

Re: Migrating dmd to D?

[js.mdnq]

I believe a complete rewrite from the ground up using a fixed 
stable dmd is needed. The reason is two fold: Many things have 
been learned about the evolution of the D language over time. 
Much of the trouble of D has been stabling the D implementation 
and spec. Second, Trying to port the C++ code to D to make a D 
compiler will only multiply the bugs in DMD. (i.e., it will 
introduce new bugs from the conversion and retain the old bugs)


Instead, I believe proper project management is needed along with 
a SOLID language specification and clear delineation of goals. If 
the language spec itself is flawed then the same things will 
occur as is with DMD.


To tie the dependence on C/C++ the D compiler would need to be 
written in the language subset of the intersection between DMD 
and the new language spec. This should not be hard to do but must 
be strictly maintained. Else one will always require dmd to 
compile the compiler.


Hence, a solid language spec for the new D compiler is needed. 
The language spec must overlap with the old spec and the D 
compiler must only be written in this overlap. (It should be 
obvious but this allows the D compiler to be compiled in DMD or 
itself, after the bootstrap one can gradually evolve the subset 
to include the newer features a few versions behind since the old 
dmd is not needed)


The problem with such an undertaking behind successful is all in 
the project management. I would say we need a solid language spec 
and the subset between it and the current spec(frozen at some 
point). I imagine they would be almost identical so actually 
little real work would be needed.


So, who's up for writing the D 3.0 spec?

Re: Are there any default dmd optimizations

[Andrej Mitrovic]

On 2/28/13, Timon Gehr  wrote:
> It's really easy. DMD can be convinced to do a sufficient conservative
> analysis even now, but the behaviour is undocumented and seems
> unintentional.
>
>
>  void main() {
>  void foo()() { bar(); }
>  void bar()() { i = 3; }
>  int i;
>  foo();
>  }

You can even make them non-templates if they're part of a mixin template.

mixin template T()
{
void foo() { bar(); }
void bar() { i = 3; }
int i;
}

void main()
{
mixin T!();
foo();
}

Re: Migrating dmd to D?

[Arlen]

On Wed, Feb 27, 2013 at 6:37 PM, Andrei Alexandrescu <
seewebsiteforem...@erdani.org> wrote:

> Hello,
>
>
> Walter and I have had a long conversation about the next radical thing to
> do to improve D's standing. Like others in this community, we believe it's
> a good time to consider bootstrapping the compiler. Having the D compiler
> written in D has quite a few advantages, among which taking advantages of
> D's features and having a large codebase that would be its own test harness.
>
> By this we'd like to initiate a dialog about how this large project can be
> initiated and driven through completion. Our initial basic ideas are:
>
> 1. Implement the dtoh standalone program that takes a D module and
> generates its corresponding C++ header.
>
> 2. Use dtoh to initiate and conduct an incremental port of the compiler.
> At given points throughout the code D code will coexist and link with C++
> code.
>
> 3. At a point in the future the last C++ module will be replaced with a D
> module. Going forward there will be no more need for a C++ compiler to
> build the compiler (except as a bootstrapping test).
>
> It is essential that we get support from the larger community for this.
> This is a large project that should enjoy strong leadership apart from
> Walter himself (as he is busy with dynamic library support which is
> strategic) and robust participation from many of us.
>
> Please chime in with ideas on how to make this happen.
>
>
> Thanks,
>
> Andrei
>

Having ported Boost.units to D, I can attest to this being a lot of work.
I did try translating first and then refactoring the code, but that did not
go well, mainly because of all the tricks and hacks employed when doing
template meta-programming in C++ that did not translate well at all to D.
With my first attempt I pretty much ended up with C++ code that was written
in D, and that's not what I wanted.  So I had to start over, refactoring
and writing D code in D as I went.  The problem with refactoring is that
once you refactor a piece, chances are that you will need to refactor
everything that depends on the code that was refactored, and that starts a
domino effect.

Of course, things are different with DMD, so translating first and then
refactoring is probably the right way to do it. But, I don't see how we
could use D's nice features without refactoring.  So, I presume this is
going to be done in two phases:

Phase 1: direct translation to make sure everything works.
Phase 2: refactoring to use D's nice features.

And your three steps would be describing Phase 1.


Arlen

Re: Are there any default dmd optimizations

[Timon Gehr]

On 02/28/2013 05:55 AM, Walter Bright wrote:

On 2/27/2013 8:01 PM, deadalnix wrote:

Plus, this is really hard to ensure that everything is initialized
properly
without going eager with setting to init.


Yeah, the forward reference order of evaluation thingie.


It's really easy. DMD can be convinced to do a sufficient conservative 
analysis even now, but the behaviour is undocumented and seems 
unintentional.



void main() {
void foo()() { bar(); }
void bar()() { i = 3; }
int i;
foo();
}

It's a fine idea to disallow the use of both a shadowed and the 
shadowing symbol in the same function anyway, so we wouldn't lose a lot 
by allowing forward references from local functions.


Then the template behaviour could be fixed:

int i = 0;

void main(){
void foo(int x){ i = x; }
foo(1);
int i = 0;
foo(2);
assert(.i==2&&i==0);
}

int i = 0;

void main(){
void foo(int x){ i = x; }
// foo(1);
int i = 0;
foo(2);
assert(.i==0&&.i==2);
}

(Currently, presence of one call can magically influence the behaviour 
of other calls.)

Re: Proposal for SentinelInputRange

[FG]

On 2013-02-28 17:43, Walter Bright wrote:

Consider the following code from lexer.c:

p++;
switch (*p)

Written using an InputRange:

popFront();
switch (front)

That code is INVALID. This is why a SentinelInputRange is necessary. You can't
just use an InputRange in an invalid manner by convention.




I do not understand... Why make a special type of InputRange when you can 
achieve exactly that with a normal string with an added extra '\0' at the end 
and then use it without any calls to empty():


while(1) {
...
popFront();
switch(front) {
case '\0': return;
...
}
}

Cstrings are a very special case because we know the terminator beforehand and 
the check is trivial CPU-wise.

Re: Proposal for SentinelInputRange

[Andrei Alexandrescu]

On 2/28/13 1:42 PM, Dmitry Olshansky wrote:

That's the wrong one. This is the one:
https://github.com/Hackerpilot/Dscanner/tree/range-based-lexer

Though feel free to destroy the other one too ;)
But I need your full powers with Dscanner first :o)


Whoa, that looks really good!

Andrei

Re: Proposal for SentinelInputRange

[Jonathan M Davis]

On Thursday, February 28, 2013 08:52:45 Walter Bright wrote:
> I've given you two examples (lexer and regexp) where you are certainly not
> stuck with that, and those two cases matter.
> 
> > Pure input ranges fail utterly as you can't save them, so you get _zero_
> > lookahead [...]

My point is that in almost all cases, what'll end up happening with a sentinel 
range which is something like this:

struct SRange(R)
    if(is(Unqual!(ElementType!R) == char))
{
    enum char sentinel = 0;

    @property char front() { return _front; }
    @property bool empty() { return _front == sentinel; }
    void popFront()
    {
        _range.popFront();
        if(_range.empty)
            _front = sentinel;
    }

    this(R range)
    {
        if(_range.empty)
            _front = sentinel;
        else
            _front = _rang.front;
    }

private:
    char _front;
    R _range;
}

Notice that it has to check for empty every time that the front is popped, and 
it can't avoid that, because it's wrapping another range which is not a 
sentinel range. The only time that it can avoid that is if it's managing its 
own memory internally via an array or pointer or whatnot. And if it's just 
going to be a string or an array, I'd argue for simply special casing strings 
or arrays to skip unnecessary empty checks.

Also, with sentinel ranges, you'll be forced to wrap strings because of that 
sentinel marker that's required for isSentinelRange, meaning that you'll get 
something like

struct SRange
{
    enum char sentinel = 0;

    @property char front() { return _front; }
    @property bool empty() { return _front == sentinel; }
    void popFront() { _str = _str[1 .. $]; }

    this(string str)
    {
        _str = str;

        if(_str.empty)
            _str = [sentinel];
        else if(_str[$ - 1] != sentinel)
            _str ~= sentinel;
    }

private:
    string _str;
}

And while the compiler will hopefully optimize away all of the extra overhead 
of the wrapper type, any functions which would be able to optimize what 
they're doing for a string or array will not special case for this wrapper 
type, because they probably won't even know about it. A prime case where that 
might be an issue would be with std.utf.decode or std.utf.decodeFront which do 
some special casing for strings and which any unicode-aware lexer would have 
to use at least some of the time (even if the vast majority of the time, it 
can just check ASCII stuff).

So, for the most part, the only time that you'll get any performance boost out 
of this is with strings or arrays, and you'll take a performance hit if you're 
using functions which special case strings or arrays but not the wrapper 
sentinel type. And yet special-casing strings and arrays will give you exactly 
the same performance boost without this sentinel range concept.

- Jonathan M Davis

Re: Proposal for SentinelInputRange

[Brian Schott]

On Thursday, 28 February 2013 at 18:38:59 UTC, Andrei 
Alexandrescu wrote:
I think that's a good idea but I took a look at 
https://github.com/bhelyer/std.d.lexer/blob/master/std/d/lexer.d 
and I will destroy it. In a good sense :o).


Andrei


https://github.com/Hackerpilot/Dscanner/blob/range-based-lexer/std/d/lexer.d
He's talking about this one.

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 22:38, Andrei Alexandrescu пишет:

On 2/28/13 12:20 PM, Dmitry Olshansky wrote:

28-Feb-2013 19:31, Andrei Alexandrescu пишет:

On 2/28/13 5:54 AM, Walter Bright wrote:

On 2/27/2013 11:55 PM, Jonathan M Davis wrote:

Again, please see how lexer.c works. I assure you, there is no double
copying going on, nor is there a double test for the terminating 0.


I know what the lexer does, and remember that it _doesn't_ operate on
ranges,
and there are subtle differences between being able to just use char*
and
trying to handle generic ranges.


Hence the need to invent SentinelInputRange.


I don't think the sentinel input range is a blocker for redoing the
parser (with ranges) in D. This discussion has probably run its course.




The right thing to do at this point is port the lexer and figure what
primitives are necessary from its input.



No need to port - look at std.d.lexer again. It was revamped and is
ready for the new round of review I should say. Let's not use the old
source for the new module and go the long path of :
split off --> port --> patch up --> D-ify & re-write to ranges

Instead we can just tweak the current std.d.lexer a little bit more and
we have good clean-room lexer written in the idiomatic D. Well, it's
getting there w.r.t. idiomaticness but it supports ranges including both
random-access and forward ones (by transparently specializing for each
one).


I think that's a good idea but I took a look at
https://github.com/bhelyer/std.d.lexer/blob/master/std/d/lexer.d and I
will destroy it. In a good sense :o).


That's the wrong one. This is the one:
https://github.com/Hackerpilot/Dscanner/tree/range-based-lexer

Though feel free to destroy the other one too ;)
But I need your full powers with Dscanner first :o)


Andrei



--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 22:08, Timon Gehr пишет:

On 02/28/2013 05:48 PM, Dmitry Olshansky wrote:

...

line 300:
 case 0x1A:  // ^Z means end of file
 case 0:
 break;

On the lines you noted it claimed that that 0x1a is outdate. Along with
the fact that you allocate filesize+2 and fill the last 2 bytes with
zeros.

In any case I see 0 and 0x1a as 2 values that act like sentinels i.e. a
tuple. And this is what spec says - any one of them is a sentinel.
Correct me if I'm wrong.



A sentinel is some data the original data is augmented with in order to
simplify its processing.


I thought 0 was proposed as such. Might have misunderstood the proposition.


The lexer acts the same on 0x1A and 0, but only the additional 0 at the
end which does not occur in the input is the sentinel.



That would mean that when you see 0 or 0x1A you do a check to see if 
that's the end of input then decide it's really the end of input.


If that's the intended behavior I fail to decipher it from  here:
http://dlang.org/lex.html#EndOfFile


The lexer may
even encounter a 0 that is not a sentinel.



--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Andrei Alexandrescu]

On 2/28/13 12:20 PM, Dmitry Olshansky wrote:

28-Feb-2013 19:31, Andrei Alexandrescu пишет:

On 2/28/13 5:54 AM, Walter Bright wrote:

On 2/27/2013 11:55 PM, Jonathan M Davis wrote:

Again, please see how lexer.c works. I assure you, there is no double
copying going on, nor is there a double test for the terminating 0.


I know what the lexer does, and remember that it _doesn't_ operate on
ranges,
and there are subtle differences between being able to just use char*
and
trying to handle generic ranges.


Hence the need to invent SentinelInputRange.


I don't think the sentinel input range is a blocker for redoing the
parser (with ranges) in D. This discussion has probably run its course.




The right thing to do at this point is port the lexer and figure what
primitives are necessary from its input.



No need to port - look at std.d.lexer again. It was revamped and is
ready for the new round of review I should say. Let's not use the old
source for the new module and go the long path of :
split off --> port --> patch up --> D-ify & re-write to ranges

Instead we can just tweak the current std.d.lexer a little bit more and
we have good clean-room lexer written in the idiomatic D. Well, it's
getting there w.r.t. idiomaticness but it supports ranges including both
random-access and forward ones (by transparently specializing for each
one).


I think that's a good idea but I took a look at 
https://github.com/bhelyer/std.d.lexer/blob/master/std/d/lexer.d and I 
will destroy it. In a good sense :o).


Andrei

Re: Are there any default dmd optimizations

[foobar]

On Wednesday, 27 February 2013 at 21:57:06 UTC, Andrei 
Alexandrescu wrote:

On 2/27/13 3:16 PM, Jacob Carlborg wrote:

On 2013-02-27 14:29, Andrei Alexandrescu wrote:

Four years ago I would've entirely agreed. But right now it's 
an odd
comment to make seeing as we're discussing all major 
decisions in this

group and we're switching full-bore to DIPs.


The "alias this" syntax the foobar mentioned was removed under 
the radar

and only discussed in a pull request.


I agree we were sloppy on that. Kenji was feeling strong about 
and Walter and I didn't have particular objections, so we gave 
him green light. In the process we neglected backward 
compatibility.


Andrei


At a bare minimum, there should be a well defined place to notify 
*users* (NOT DMD contributers) about language changes *ahead of 
time*. If such place is not defined, than people do not know 
where to look for that info if that is even available at all. 
This at least will remove the element of surprise.


For D to be really open as it claims to be, there should be 
additional guidelines about the decision making process itself. 
This should be made accessible for *users* (D programmers). I 
need not be a core DMD contributer, nor should I need to know C++ 
or DMD's internals, Nor should I need to browse among hundreds of 
bugs on bugzilla or pull requests on github (both can be labeled 
very poorly) to discern out of that sea of information what are 
the *few* visible changes to the language and core library APIs.

Re: Proposal for SentinelInputRange

[deadalnix]

On Thursday, 28 February 2013 at 17:00:51 UTC, Walter Bright 
wrote:

On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:
If this doesn't translate to the same code, I don't know why 
not.


Try it and see with your favorite C compiler.

Then try the lookahead cases I also posted.


You are being stubborn here.

You claim that this is significantly faster, but give no numbers.
You claim that the compiler can't do some optimization, when LLVM 
does it already.


See sample code bellow, which is a typical structure find in 
lexer.c :


int bar(int n) {
switch(n) {
case 0:
return 0; // Bad case !

case 25:
return 75;

case 42:
return 69;

case 666:
return 999;

default:
return -1;
}
}

int foo(int n) {
switch(n) {
case 1:
return 23;

case 2:
case 3:
return n;

default:
return bar(n);
}
}

As we see, foo don't check for 0, and bar does, but only when 
necessary, as bar isn't called. Or this is what you think. Let's 
see how SDC compile this :


define i32 @_D3barFiZi(i32 %arg.n) {
  %n = alloca i32
  store i32 %arg.n, i32* %n
  br label %body

body: ; preds = %0
  %1 = load i32* %n
  switch i32 %1, label %default [
i32 0, label %.case
i32 25, label %.case1
i32 42, label %.case2
i32 666, label %.case3
  ]

switchstart:  ; No 
predecessors!

  br label %.case

.case:; preds = 
%body, %switchstart

  ret i32 0

.case1:   ; preds = %body
  ret i32 75

.case2:   ; preds = %body
  ret i32 69

.case3:   ; preds = %body
  ret i32 999

default:  ; preds = %body
  ret i32 -1

switchend:; No 
predecessors!

  unreachable
}

define i32 @_D3fooFiZi(i32 %arg.n) {
  %n = alloca i32
  store i32 %arg.n, i32* %n
  br label %body

body: ; preds = %0
  %1 = load i32* %n
  switch i32 %1, label %default [
i32 1, label %.case
i32 2, label %.case1
i32 3, label %.case2
  ]

switchstart:  ; No 
predecessors!

  br label %.case

.case:; preds = 
%body, %switchstart

  ret i32 23

.case1:   ; preds = %body
  br label %.case2

.case2:   ; preds = 
%body, %.case1

  %2 = load i32* %n
  ret i32 %2

default:  ; preds = %body
  %3 = load i32* %n
  %4 = call i32 @_D3barFiZi(i32 %3)
  ret i32 %4

switchend:; No 
predecessors!

  unreachable
}

Here is the raw result of the frontend in LLVM IR. Now here is 
what the optimizer give us :


define i32 @_D3barFiZi(i32 %arg.n) nounwind readnone {
body:
  switch i32 %arg.n, label %default [
i32 0, label %.case
i32 25, label %.case1
i32 42, label %.case2
i32 666, label %.case3
  ]

.case:; preds = 
%default, %.case3, %.case2, %.case1, %body
  %merge = phi i32 [ 0, %body ], [ 75, %.case1 ], [ 69, %.case2 
], [ 999, %.case3 ], [ -1, %default ]

  ret i32 %merge

.case1:   ; preds = %body
  br label %.case

.case2:   ; preds = %body
  br label %.case

.case3:   ; preds = %body
  br label %.case

default:  ; preds = %body
  br label %.case
}

define i32 @_D3fooFiZi(i32 %arg.n) nounwind readnone {
body:
  switch i32 %arg.n, label %default.i [
i32 1, label %.case
i32 2, label %.case2
i32 3, label %.case2
i32 0, label %_D3barFiZi.exit
i32 25, label %.case1.i
i32 42, label %.case2.i
i32 666, label %.case3.i
  ]

.case:; preds = 
%body, %_D3barFiZi.exit, %.case2
  %merge = phi i32 [ 23, %body ], [ %arg.n, %.case2 ], [ 
%merge.i, %_D3barFiZi.exit ]

  ret i32 %merge

.case2:   ; preds = 
%body, %body

  br label %.case

.case1.i: ; preds = %body
  br label %_D3barFiZi.exit

.case2.i: ; preds = %body
  br label %_D3barFiZi.exit

.case3.i: ; preds = %body
  br label %_D3barFiZi.exit

de

Re: Proposal for SentinelInputRange

[Timon Gehr]

On 02/28/2013 05:48 PM, Dmitry Olshansky wrote:

...

line 300:
 case 0x1A:  // ^Z means end of file
 case 0:
 break;

On the lines you noted it claimed that that 0x1a is outdate. Along with
the fact that you allocate filesize+2 and fill the last 2 bytes with zeros.

In any case I see 0 and 0x1a as 2 values that act like sentinels i.e. a
tuple. And this is what spec says - any one of them is a sentinel.
Correct me if I'm wrong.



A sentinel is some data the original data is augmented with in order to 
simplify its processing.


The lexer acts the same on 0x1A and 0, but only the additional 0 at the 
end which does not occur in the input is the sentinel. The lexer may 
even encounter a 0 that is not a sentinel.

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 21:38, deadalnix пишет:

On Thursday, 28 February 2013 at 17:13:36 UTC, Dmitry Olshansky wrote:

No as a compiler will take it (or may depending on its brain) that 0
is what you want to test *first*. It may speed things up if branch is
almost always taken but its not the case with sentinel. Thus its jsut
dead code that needs to be decoded, evalutated and skipped (as
predicated) *before* doing switch jump.

In fact some people avoid the overhead of switch by placing one or two
of highly-frequent branches with tests before the switch (thus
avoiding indirect branch it entails in these frequent cases).


That won't work as expected with LLVM and full optimizations, as it will
combine everything in a switch, unless you use branch weight, in which
case it can do the reverse : extract common cases from the switch.

See : http://llvm.org/docs/BranchWeightMetadata.html

Mn I missed this point. Seems cool unlike relying on it doing magic 
behind the senescence. Then I stand corrected.



GCC does something similar.





--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 21:38, deadalnix пишет:

On Thursday, 28 February 2013 at 17:13:36 UTC, Dmitry Olshansky wrote:

No as a compiler will take it (or may depending on its brain) that 0
is what you want to test *first*. It may speed things up if branch is
almost always taken but its not the case with sentinel. Thus its jsut
dead code that needs to be decoded, evalutated and skipped (as
predicated) *before* doing switch jump.

In fact some people avoid the overhead of switch by placing one or two
of highly-frequent branches with tests before the switch (thus
avoiding indirect branch it entails in these frequent cases).


That won't work as expected with LLVM and full optimizations, as it will
combine everything in a switch, unless you use branch weight, in which
case it can do the reverse : extract common cases from the switch.

See : http://llvm.org/docs/BranchWeightMetadata.html

GCC does something similar.

This is another example of how people think they are doing high level
assembly when in fact, the compiler is changing everything behind their
back, and not doing at all what they think.


Depends on the brains of compiler like I said. BTW it can't know the 
most frequent branches so jump-table may be actually slower (in some 
cases though they are niche).


--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Ary Borenszweig]

On 2/28/13 2:32 PM, Steven Schveighoffer wrote:

On Thu, 28 Feb 2013 12:13:27 -0500, Dmitry Olshansky
 wrote:


No as a compiler will take it (or may depending on its brain) that 0
is what you want to test *first*. It may speed things up if branch is
almost always taken but its not the case with sentinel. Thus its jsut
dead code that needs to be decoded, evalutated and skipped (as
predicated) *before* doing switch jump.


Well, according to lexer.c, case 0 is the first case.  Why does that not
make the compiler decide to test 0 first?

Answer: it actually doesn't care, the switch compiles to a jump table.
Which still begs the question, why can't the compiler make the leap to
the equivalent code with a range?

are these not semantically equivalent?

if(x == 0)
{
// case for 0
}
else
{
switch(x)
{
   case 1:
  // case for 1;
  break;
   case 2:
  // case for 2;
  break;
   ... // cases for everything but 0
}
}

vs.

switch(x)
{
case 0:
   // case for 0;
   break;
case 1:
   // case for 1;
   break;
case 2:
   // case for 2;
   break;
... // cases for everything but 0
}

They seem semantically identical.  It would not be impossible for an
optimizer to make this leap.

Combined with inlining, the above could be:

if(r.empty)
{
// case for 0;
}
else
   ...

and still be optimized the same.  I'm not saying it happens, I'm saying
it's possible.  I have read several posts here claiming that llvm does
this (I haven't tried this myself, but it sounds likely true).


It is true. Compiling this Crystal program:

---
def my_fun(num)
  num == 0
end

num = ARGV[0].to_i

if my_fun(num)
  puts 0
else
  case num
  when 1
puts 1
  when 2
puts 2
  end
end
---

I see this somewhere in the generated llvm code:

switch i32 %25, label %crystal_main.exit [
i32 0, label %then.i
i32 1, label %then16.i
i32 2, label %then20.i
  ]

Re: Migrating dmd to D?

[Timon Gehr]

On 02/28/2013 03:02 PM, Jacob Carlborg wrote:

On 2013-02-28 11:25, Walter Bright wrote:


Why? The only point would be to change the license of the front end.


I don't know, I'm not doing it. Possibly reasons:

* Fun


Yup.


...
* Change the license


Actually I dislike the whole licensing issue.


* DMD is not written in D


Yup.


* DMD is not built/usable as a library


Yup. There should be a sufficiently simple frontend on which libraries 
for source code analysis and manipulation tools can be built.



* DMD contains a lot of bugs



Yup, even the intention on the compiler developer side is buggy 
sometimes. DMD will keep breaking my code because the hand-wavy notion 
of a "forward reference error" somehow appears to be accepted.


* Having only one implementation harms the language quality, because 
people are more likely to be willing to accept arguably buggy or stupid 
behaviour, and there is no pressure to clarify details of the spec. (eg. 
UDA's in DMD introduce an awkward and underpowered AST macro system. 
Value range propagation is too conservative for bitwise operations, DMD 
contains undocumented features, like types as function arguments in a 
typeof, or invoking opCall via an assignment, etc.)


* wc -l reveals that the DMD front end source code is roughly 30 to 40 
times larger than it should be for what it does in my opinion. 
Refactoring it so that it shrinks by that factor in C++ is a lot harder 
than building it from scratch in D.



(* Knowing the guts of a front end means you can decide to add type 
system and syntax extensions for private use. :P)



Although I don't know for sure if they're clean room implementations or
not. They are at least not direct translations.



Mine is clean room.

Re: Unittests and assert

[H. S. Teoh]

On Thu, Feb 28, 2013 at 04:31:15PM +0100, Andrej Mitrovic wrote:
> On 2/28/13, H. S. Teoh  wrote:
> > Hmm. I was using assertNotThrown... which disappears with -release.
> 
> This shouldn't happen. Could you provide a test-case, I can't recreate
> this behavior.

Ugh. While trying to reduce the failing test case, I discovered that
assertNotThrown is actually working correctly. There appears to be some
kind of subtle bug in my code related to assert() being called in an
in-contract, that causes a side-effect that changes the result of the
test.

IOW, my fault, there's nothing wrong with assert/unittest. Sorry for the
false alarm. :-( :-(


T

-- 
All problems are easy in retrospect.

Re: Proposal for SentinelInputRange

[deadalnix]

On Thursday, 28 February 2013 at 17:13:36 UTC, Dmitry Olshansky 
wrote:
No as a compiler will take it (or may depending on its brain) 
that 0 is what you want to test *first*. It may speed things up 
if branch is almost always taken but its not the case with 
sentinel. Thus its jsut dead code that needs to be decoded, 
evalutated and skipped (as predicated) *before* doing switch 
jump.


In fact some people avoid the overhead of switch by placing one 
or two of highly-frequent branches with tests before the switch 
(thus avoiding indirect branch it entails in these frequent 
cases).


That won't work as expected with LLVM and full optimizations, as 
it will combine everything in a switch, unless you use branch 
weight, in which case it can do the reverse : extract common 
cases from the switch.


See : http://llvm.org/docs/BranchWeightMetadata.html

GCC does something similar.

This is another example of how people think they are doing high 
level assembly when in fact, the compiler is changing everything 
behind their back, and not doing at all what they think.

Re: Request for comments: std.d.lexer

[Dmitry Olshansky]

28-Feb-2013 21:27, Dmitry Olshansky пишет:

28-Feb-2013 13:09, Brian Schott пишет:

On Saturday, 9 February 2013 at 07:55:04 UTC, Walter Bright wrote:

On 2/4/2013 7:19 PM, Brian Schott wrote:

Still only half speed. I'm becoming more and more convinced that
Walter is
actually a wizard.


I worship the Dark Arts.


*recites incantations*
*merges pull requests*
*adds unit tests*

http://hackerpilot.github.com/experimental/std_lexer/images/times4.png


Looking far better now. Keep in mind that we still don't use the
original dmd's sentinel magic to avoid length check in std.d.lexer :)

Being that wizard who gave a couple of scrolls to Brain I'll outline
some interesting data points collected while helping him out.



To clarify these are problems I observed but haven't solved/avoided 
completely:



- D run-time takes some time to start up/shut down. It's on the order of
1ms for me vs 1/10th of ms for plain C
- expanding on the previous point - GC.malloc takes sometime and
triggers collections from time to time (2 collections to lex datetime,
there is next to no garbage, but they run regardless).



And this one below is an experiment and not is not related to the 
numbers posted still.



Even simply disabling GC at first and re-enabling it at the end of
program speeds up the whole time by roughly 5% on my machine.



--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Steven Schveighoffer]

On Thu, 28 Feb 2013 12:13:27 -0500, Dmitry Olshansky  
 wrote:


No as a compiler will take it (or may depending on its brain) that 0 is  
what you want to test *first*. It may speed things up if branch is  
almost always taken but its not the case with sentinel. Thus its jsut  
dead code that needs to be decoded, evalutated and skipped (as  
predicated) *before* doing switch jump.


Well, according to lexer.c, case 0 is the first case.  Why does that not  
make the compiler decide to test 0 first?


Answer: it actually doesn't care, the switch compiles to a jump table.   
Which still begs the question, why can't the compiler make the leap to the  
equivalent code with a range?


are these not semantically equivalent?

if(x == 0)
{
   // case for 0
}
else
{
   switch(x)
   {
  case 1:
 // case for 1;
 break;
  case 2:
 // case for 2;
 break;
  ... // cases for everything but 0
   }
}

vs.

switch(x)
{
   case 0:
  // case for 0;
  break;
   case 1:
  // case for 1;
  break;
   case 2:
  // case for 2;
  break;
   ... // cases for everything but 0
}

They seem semantically identical.  It would not be impossible for an  
optimizer to make this leap.


Combined with inlining, the above could be:

if(r.empty)
{
   // case for 0;
}
else
  ...

and still be optimized the same.  I'm not saying it happens, I'm saying  
it's possible.  I have read several posts here claiming that llvm does  
this (I haven't tried this myself, but it sounds likely true).


-Steve

Re: Request for comments: std.d.lexer

[Dmitry Olshansky]

28-Feb-2013 13:09, Brian Schott пишет:

On Saturday, 9 February 2013 at 07:55:04 UTC, Walter Bright wrote:

On 2/4/2013 7:19 PM, Brian Schott wrote:

Still only half speed. I'm becoming more and more convinced that
Walter is
actually a wizard.


I worship the Dark Arts.


*recites incantations*
*merges pull requests*
*adds unit tests*

http://hackerpilot.github.com/experimental/std_lexer/images/times4.png


Looking far better now. Keep in mind that we still don't use the 
original dmd's sentinel magic to avoid length check in std.d.lexer :)


Being that wizard who gave a couple of scrolls to Brain I'll outline 
some interesting data points collected while helping him out.


- D run-time takes some time to start up/shut down. It's on the order of 
1ms for me vs 1/10th of ms for plain C
- expanding on the previous point - GC.malloc takes sometime and 
triggers collections from time to time (2 collections to lex datetime, 
there is next to no garbage, but they run regardless).


Even simply disabling GC at first and re-enabling it at the end of 
program speeds up the whole time by roughly 5% on my machine.


- opApply is definitely slower then inlined range-based foreach loop 
even with scope delegate.


Other then this specifics the prime spells that give the performance are:

- don't use built-in AA or subtle allocations (avoid GC as far as you can)

- lean common path, keep there only the operations that are required in 
*every* code-path


- avoid ever doing the same work twice (redesign, hack and whatnot but 
don't do it)



--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Steven Schveighoffer]

On Thu, 28 Feb 2013 12:00:48 -0500, Walter Bright  
 wrote:



On 2/28/2013 6:31 AM, Steven Schveighoffer wrote:

If this doesn't translate to the same code, I don't know why not.


Try it and see with your favorite C compiler.


A sample case of 1 does not prove it's not possible, or explain why those  
optimizers don't take that step.  A valid response would be to give a case  
why an optimizer COULDN'T make that leap.



Then try the lookahead cases I also posted.


You have already stated it gets changed into a jump table.  Such an  
optimization seems possible to me, even with the != 0 check outside the  
switch, even if not all C compilers employ it.


-Steve

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 19:31, Andrei Alexandrescu пишет:

On 2/28/13 5:54 AM, Walter Bright wrote:

On 2/27/2013 11:55 PM, Jonathan M Davis wrote:

Again, please see how lexer.c works. I assure you, there is no double
copying going on, nor is there a double test for the terminating 0.


I know what the lexer does, and remember that it _doesn't_ operate on
ranges,
and there are subtle differences between being able to just use char*
and
trying to handle generic ranges.


Hence the need to invent SentinelInputRange.


I don't think the sentinel input range is a blocker for redoing the
parser (with ranges) in D. This discussion has probably run its course.




The right thing to do at this point is port the lexer and figure what
primitives are necessary from its input.



No need to port - look at std.d.lexer again. It was revamped and is 
ready for the new round of review I should say. Let's not use the old 
source for the new module and go the long path of :

split off --> port --> patch up --> D-ify & re-write to ranges

Instead we can just tweak the current std.d.lexer a little bit more and 
we have good clean-room lexer written in the idiomatic D. Well, it's 
getting there w.r.t. idiomaticness but it supports ranges including both 
random-access and forward ones (by transparently specializing for each 
one).

--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Steven Schveighoffer]

On Thu, 28 Feb 2013 12:02:53 -0500, Walter Bright  
 wrote:



On 2/28/2013 7:40 AM, Steven Schveighoffer wrote:

If you look at lexer.c, case 0 is the first test.


No, it is not. It is actually a table lookup - all done in parallel.

 jmp cases[character]



You are comparing the assembly output of your solution with uncompiled D  
code.  Apples and oranges.


Quoting directly from  
https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c#L479:


switch (*p)
{
case 0:

As several others have pointed out, an optimizer can (and some do) make  
this rewrite automatically.


The point is, if the lexer simply requires an input range, and not a  
sentinel input range, it is more flexible for its input.  But when it does  
get called with a sentinel input range, the optimizer can reap the  
benefits.


-Steve

Re: Migrating dmd to D?

[Iain Buclaw]

On 28 February 2013 16:01, Andrei Alexandrescu <
seewebsiteforem...@erdani.org> wrote:

> On 2/28/13 10:53 AM, Iain Buclaw wrote:
>
>> On 28 February 2013 15:24, Andrei Alexandrescu
>> > > >>
>>
>> wrote:
>>
>> On 2/28/13 5:03 AM, deadalnix wrote:
>>
>> That will impair GDC and LDC quite a lot.
>>
>>
>> Let's see what the respective project leaders say.
>>
>> Andrei
>>
>>
>>
>> I'll provide facts, but I'll reserve any opinion to myself.
>>
>> So, feel free to send me a list of questions you want me to answer. :o)
>>
>
> "Would an initiative of porting dmd to D create difficulties for gdc?"
>
> Andrei
>


Gnat's frontend is written in Ada, however it does not depend on having to
call anything from the gcc backend.

We still do not know what portions of the frontend is being ported over to
D.  The way gdc is written, it takes the D Frontend, removes all C++ parts
that interface with dmd's backend - toElem; toIR; toObjFile; toSymbol;
toCtype; toDt (this latter one I am in the middle of removing from gdc) and
implements them to instead build GCC trees, the code itself also being in
C++.

These are all methods defined in D Front-End, and rely on calling and
interfacing with the gcc backend.  Re-writing these in D is not an option,
as require access to GCC macros.

See tree.h for the majority of that list:
http://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=gcc/tree.h;hb=refs/heads/master


-- 
Iain Buclaw

*(p < e ? p++ : p) = (c & 0x0f) + '0';

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 21:09, Steven Schveighoffer пишет:

On Thu, 28 Feb 2013 11:43:06 -0500, Walter Bright
 wrote:


On 2/28/2013 6:59 AM, Andrei Alexandrescu wrote:

On 2/28/13 2:37 AM, deadalnix wrote:

I don't see how defining a specific sentinel range here helps.


On first blush I agree. It may as well be a range that by convention is
sentinel-terminated, and there's calls to front and popFront but
never to empty.



Consider the following code from lexer.c:

p++;
switch (*p)

Written using an InputRange:

popFront();
switch (front)

That code is INVALID. This is why a SentinelInputRange is necessary.
You can't just use an InputRange in an invalid manner by convention.


Does switch(*p) include a case for 0?  If so, wouldn't it be equivalent
to say if(empty) /* do stuff that case 0 does */ else switch(front)

-Steve


No as a compiler will take it (or may depending on its brain) that 0 is 
what you want to test *first*. It may speed things up if branch is 
almost always taken but its not the case with sentinel. Thus its jsut 
dead code that needs to be decoded, evalutated and skipped (as 
predicated) *before* doing switch jump.


In fact some people avoid the overhead of switch by placing one or two 
of highly-frequent branches with tests before the switch (thus avoiding 
indirect branch it entails in these frequent cases).


--
Dmitry Olshansky

Re: Proposal for SentinelInputRange

[Andrei Alexandrescu]

On 2/28/13 11:54 AM, Walter Bright wrote:

On 2/28/2013 7:31 AM, Andrei Alexandrescu wrote:

I don't think the sentinel input range is a blocker for redoing the
parser (with
ranges) in D. This discussion has probably run its course. The right
thing to do
at this point is port the lexer and figure what primitives are
necessary from
its input.


I don't agree. It is a blocker for getting a fast lexer.


I don't think what I said was understood.

Andrei

Re: Proposal for SentinelInputRange

[Steven Schveighoffer]

On Thu, 28 Feb 2013 11:43:06 -0500, Walter Bright  
 wrote:



On 2/28/2013 6:59 AM, Andrei Alexandrescu wrote:

On 2/28/13 2:37 AM, deadalnix wrote:

I don't see how defining a specific sentinel range here helps.


On first blush I agree. It may as well be a range that by convention is
sentinel-terminated, and there's calls to front and popFront but never  
to empty.



Consider the following code from lexer.c:

p++;
switch (*p)

Written using an InputRange:

popFront();
switch (front)

That code is INVALID. This is why a SentinelInputRange is necessary. You  
can't just use an InputRange in an invalid manner by convention.


Does switch(*p) include a case for 0?  If so, wouldn't it be equivalent to  
say if(empty) /* do stuff that case 0 does */ else switch(front)


-Steve

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 20:56, Walter Bright пишет:

On 2/28/2013 7:41 AM, Dmitry Olshansky wrote:

The merit of sentinel range IMHO is largely in tapping into C-strings
and the
like more naturally.


The merit is having significantly faster speed.



5% is good but doesn't count as significant. But that was for std.regex 
quite sometime ago. In the lexer it might get be more.


I can try right away with std.d.lexer by Brain Schott and get rid of the 
check for the length and place a null byte right after the file buffer. 
Then I should be able to estimate the gain.


--
Dmitry Olshansky

Re: New std.uni: ready for more beating

[Zach the Mystic]

On Thursday, 28 February 2013 at 08:07:28 UTC, Jacob Carlborg 
wrote:

On 2013-02-28 01:38, Zach the Mystic wrote:


Would 'now' be even better than 'currTime'?


I think so.


Be careful what you say, or you might have to go into my 
cryogenic freezer as well!

Re: D as a prototyping language (for C/C++ projects)

[Andrei Alexandrescu]

On 2/28/13 11:36 AM, David Nadlinger wrote:

On Thursday, 28 February 2013 at 15:51:02 UTC, Andrei
Alexandrescu wrote:

On 2/28/13 10:49 AM, Andrei Alexandrescu wrote:

On 2/28/13 10:24 AM, Jacob Carlborg wrote:

That is not my idea of "tap". This is my idea of "tap":

Object (func) (Object o)
{
func(o);
return o;
}


I know. I think my tap is better than your tap.


... and closer in intent to Ruby's tap as I understand it from reading
http://ruby-doc.org/core-2.0/Object.html#method-i-tap


Ruby's tap just applies the passed block to the object it is
called on. I am not quite sure how your range idea comes into
play here?

David


Oh, I misunderstood the example at 
http://ruby-doc.org/core-2.0/Object.html#method-i-tap:


(1..10).tap {|x| puts "original: #{x.inspect}"}
  .to_a.tap {|x| puts "array: #{x.inspect}"}
  .select {|x| x%2==0} .tap {|x| puts "evens: #{x.inspect}"}
  .map { |x| x*x } .tap {|x| puts "squares: #{x.inspect}"}

It eagerly prints the entire range, then eagerly prints the entire 
array, then eagerly the entire filtered range, then eagerly the entire 
map result.


I thought it works lazily, and I think in D it should (otherwise it 
would be e.g. useless with an input range). So the D translation would be:


iota(1, 10)
  .tap!(a => writeln("original: ", a))
  .filter!(a => a % 2 == 0)
  .tap!(a => writeln("filtered: ", a))
  .map!(a => a * a)
  .tap!(a => writeln("squared: ", a));

This will produce output interleaved, so it's semantically different.

I've used something similar to "tap" in a streaming-based library for 
machine learning I worked on as a grad student. It's been instrumental 
for data analysis and debugging. This conversation reminded me of it.


So my thought on the subject - I don't care much for

T tap(alias func)(T x) { func(x); return x; }

It's the kind of chaff that doesn't do any real work and only dilutes 
the value of a library, but I do think a tap tapping into a range does 
real work and would be a valuable addition.



Andrei

Re: Proposal for SentinelInputRange

[deadalnix]

On Thursday, 28 February 2013 at 16:36:44 UTC, Walter Bright 
wrote:

On 2/28/2013 6:48 AM, Ary Borenszweig wrote:

On 2/28/13 1:57 AM, Walter Bright wrote:

On 2/27/2013 8:01 PM, John Colvin wrote:
Why must sentinel be known at compile time? I don't see 
what's in the

way of it
being a runtime argument.


Performance!

It should be usable as a case in a switch statement.


Isn't it possible for the optimizer to inline the function 
call and then combine

the next ifs?

if (isSentinel(value)) {
} else {
  switch(value) {
  case ...
  }
}


1. I don't know of any C compiler that would do that.



As mentioned, LLVM is able to do this kind of things. I have to 
admit I was quite amazed when I discovered it.



2. There are other cases, as I pointed out to deadalnix.

3. You still can't do lookahead without extra checks



You need the actual check to do proper generic D code. But the 
compiler is able to optimize it away via inlining and mecanism 
described in 1.


Once again, guys, have a look at lexer.c at the lines I pointed 
out.


I see nothing that can't be done by an optimizing compiler. Maybe 
something is, but I can't find it. And the example you pointed me 
aren't.

Re: Proposal for SentinelInputRange

[Dmitry Olshansky]

28-Feb-2013 20:52, Walter Bright пишет:

On 2/28/2013 3:29 AM, Jonathan M Davis wrote:

And you were just claiming that the lexer checked the sentinel type in
only
one place. If that's indeed the case (and I think that it's quite
close to
being true if it isn't true), then you _wouldn't_ need to use static
ifs like
this in many places. So, which is it? If you need to check the
sentinel often
enough that using static ifs is a problem, then it's probably not
buying you
much of anything over checking empty anyway.


Please, again, examine lexer.c.

For example, look at what happens after line 719. Try 794 in particular.

Now look at line 996 and what follows. Note that there is not a single
null check there, yet the code is correct and does not run off the end
of the data.



But my point is that outside of strings or arrays, you're almost
certainly
stuck with that.


I've given you two examples (lexer and regexp) where you are certainly
not stuck with that, and those two cases matter.



I'll add that when I wrote current std.regex internal VM I've switched 
to the sentinel as terminator of the program instead of checking the 
length. The end result was about 5% of speed up gained back then 
(measured on DMD alone though, other compilers didn't compile it at the 
time).


In the lexer it may help a bit more given the lookahead.

--
Dmitry Olshansky