August 26, 2008
On Tue, 26 Aug 2008 23:29:33 +0400, superdan <super@dan.org> wrote:
[snip]
>> The D spec certainly doesn't make any guarantees about
>> the time/memory complexity of opIndex; it's up to the implementing class
>> to do so.
>
> it don't indeed. it should. that's a problem with the spec.
>

I agree. You can't rely on function invokation, i.e. the following might be slow as death:

auto n = collection.at(i);
auto len = collection.length();

but index operations and properties getters should be real-time and have O(1) complexity by design.

auto n = collection[i];
auto len = collection.length;
August 26, 2008
On Tue, 26 Aug 2008 23:58:10 +0400, Denis Koroskin <2korden@gmail.com> wrote:

> On Tue, 26 Aug 2008 23:29:33 +0400, superdan <super@dan.org> wrote:
> [snip]
>>> The D spec certainly doesn't make any guarantees about
>>> the time/memory complexity of opIndex; it's up to the implementing class
>>> to do so.
>>
>> it don't indeed. it should. that's a problem with the spec.
>>
>
> I agree. You can't rely on function invokation, i.e. the following might be slow as death:
>
> auto n = collection.at(i);
> auto len = collection.length();
>
> but index operations and properties getters should be real-time and have O(1) complexity by design.
>
> auto n = collection[i];
> auto len = collection.length;

The same goes to assignment, casts, comparisons, shifts, i.e. everything that doesn't have a function invokation syntax.

BTW, that's one of the main C++ criticisms: you can't say how much time a given line may take. It is predictable in C because it lacks operator overloading.
August 26, 2008
Reply to Nick,

> "bearophile" <bearophileHUGS@lycos.com> wrote in message
> news:g8vmda$sd4$1@digitalmars.com...
> 
>> BCS:
>> 
>>> If you must have that sort of interface, pick a different language,
>>> because D isn't intended to work that way.
>>> 
>> I suggest Benji to try C# 3+, despite all the problems it has and the
>> borg-like nature of such software, etc, it will be used way more than
>> D, and it has all the nice things Benji asks for.
>> 
> (pet peeve) As much as there is that I like about C#, the lack of an
> IArithmetic or operator constrains tends to gimp its template system
> in a number of cases.
> 

C# generics are *Crippled*. They more or less do nothing but map types around.


August 26, 2008
superdan wrote:
>> Noooooooobody uses backtracking to parse.
> 
> guess that makes perl regexes et al noooooooobody.

I suppose it depends on your definition of "parse".

>> Most of the time LL(k) token lookahead solves the problem. Sometimes you need a syntactic predicate or (rarely) a semantic predicate.
>>
>> I've never even heard of a parser generator framework that supported backtracking.
> 
> live & learn. keep lookin'. hint: try antlr.

I've used ANTLR a few times. It's nice. I didn't realize it supported backtracking, though. (In my experience writing parsers, backtracking is one of those things you work overtime to eliminate, because it usually destroys performance.)

It's funny you should mention ANTLR, actually, in this discussion. A year or so ago, I was considering porting the ANTLR runtime to D. The original runtime is written in Java, and makes full use of the robust string handling capabilities of the Java standard library.

Based on the available text processing functionality in D at that time, I quickly gave up on the project as being not worth the effort.

--benji
August 26, 2008
Reply to Benji,

> superdan wrote:
> 
>> Benji Smith Wrote:
>> 
>>> I wrote a streaming CSV parser (which takes discipline to do
>>> correctly, since a double-quote enclosed field can legally contain
>>> arbitrary newline characters, and quotes are escaped by doubling).
>>> It provides a field callback and a record callback, so it's very
>>> handy for performing ETL tasks.
>>> 
>>> If I had to load the whole CSV files into memory before parsing, it
>>> wouldn't work, because sometimes they can be hundreds of megabytes.
>>> But the streaming parser takes up almost no memory at all.
>>> 
>>> --benji
>>> 
>> sure it takes very little memory. i'll tell u how much memory u need
>> in fact. it's the finite state needed by the fsa. u could do that
>> because csv only needs finite state for parsing. soon as you need to
>> backtrack stream parsing becomes very difficult.
>> 
> Noooooooobody uses backtracking to parse.
> 
> Most of the time LL(k) token lookahead solves the problem. Sometimes
> you need a syntactic predicate or (rarely) a semantic predicate.
> 
> I've never even heard of a parser generator framework that supported
> backtracking.
> 
> --benji
> 

Antlr, dparse and (IIRC) eniki all do


August 26, 2008
Denis Koroskin wrote:
>> I agree. You can't rely on function invokation, i.e. the following might be slow as death:
>>
>> auto n = collection.at(i);
>> auto len = collection.length();
>>
>> but index operations and properties getters should be real-time and have O(1) complexity by design.
>>
>> auto n = collection[i];
>> auto len = collection.length;
> 
> The same goes to assignment, casts, comparisons, shifts, i.e. everything that doesn't have a function invokation syntax.

This is the main reason I dislike D's optional parentheses for function invocations:

  something.dup; // looks cheap
  something.dup(); // looks expensive

Since any zero-arg function can have its parens omitted, it's harder to read code and see where the expensive operations are.

--benji
August 26, 2008
Reply to Benji,

> I've used ANTLR a few times. It's nice.
> 

I've used it. If you gave me the choice of sitting in a cardboard small box all day or using it again, I'll sit in the cardboard box because I fit in that box better.


August 26, 2008
Benji Smith Wrote:

> superdan wrote:
> >> Noooooooobody uses backtracking to parse.
> > 
> > guess that makes perl regexes et al noooooooobody.
> 
> I suppose it depends on your definition of "parse".

well since you was gloating about handling a csv file as "parsing" i thot i'd lower my definition accordingly :)

p.s. sorry benji. you are cool n all (tho to be brutally honest listenin' more an' talkin' less always helps) but you keep on raisin' those easy balls fer me. what can i do? i keep on dunkin'em ;)
August 26, 2008
BCS Wrote:

> Reply to Benji,
> 
> > I've used ANTLR a few times. It's nice.
> > 
> 
> I've used it. If you gave me the choice of sitting in a cardboard small box all day or using it again, I'll sit in the cardboard box because I fit in that box better.

i've used it too eh. u gotta be talking about a pretty charmin' cozy box there. the effin' mcmansion of boxes in fact. coz antlr is one of the best if not the best period.
August 26, 2008
"Denis Koroskin" wrote
> On Tue, 26 Aug 2008 23:29:33 +0400, superdan <super@dan.org> wrote: [snip]
>>> The D spec certainly doesn't make any guarantees about
>>> the time/memory complexity of opIndex; it's up to the implementing class
>>> to do so.
>>
>> it don't indeed. it should. that's a problem with the spec.
>>
>
> I agree. You can't rely on function invokation, i.e. the following might be slow as death:
>
> auto n = collection.at(i);
> auto len = collection.length();
>
> but index operations and properties getters should be real-time and have O(1) complexity by design.
>
> auto n = collection[i];
> auto len = collection.length;

less than O(n) complexity please :)  Think of tree map complexity which is usually O(lg n) for lookups.  And the opIndex syntax is sooo nice for maps :)

In general, opIndex just shouldn't imply 'linear search', as its roots come from array lookup, which is always O(1).  The perception is that x[n] should be fast.  Otherwise you have coders using x[n] all over the place thinking they are doing quick lookups, and wondering why their code is so damned slow.

-Steve