August 26, 2008
Tomas Lindquist Olsen:
> Might I ask where that site is?

I have sent you an email with information and more things, etc.

Bye,
bearophile
August 26, 2008
Denis Koroskin Wrote:

> On Wed, 27 Aug 2008 00:30:07 +0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> 
> > "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
> >
> >
> 
> Yes, that was a rash statement.

i'm kool & the gang with log n too. that's like proportional 2 the count of digits in n.

undecided about sublinear. like o(n^.5). guess that would be pushin' it. but they come by rarely so why bother makin' a decision :)
August 26, 2008
"Denis Koroskin" <2korden@gmail.com> wrote in message news:op.ugie28dxo7cclz@proton.creatstudio.intranet...
> 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;

I disagree. That strategy strikes me as a very clear example of breaking encapsulation by having implementation details dictate certain aspects of the API. At the very least, that will make the API overly rigid, hindering future changes that could otherwise have been non-breaking, behind-the-scenes changes.

For realtime code, I can see the benefit to what you're saying. Although in many cases only part of a program needs to be realtime, and for the rest of the program's code I'd hate to have to sacrifice the encapsulation benefits.


August 26, 2008
Nick Sabalausky Wrote:

> "Denis Koroskin" <2korden@gmail.com> wrote in message news:op.ugie28dxo7cclz@proton.creatstudio.intranet...
> > 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;
> 
> I disagree. That strategy strikes me as a very clear example of breaking encapsulation by having implementation details dictate certain aspects of the API. At the very least, that will make the API overly rigid, hindering future changes that could otherwise have been non-breaking, behind-the-scenes changes.

take this:

auto c = new Customer;
c.loadCustomerInfo("123-12-1234");

that's all cool. there's no performance guarantee other than some best effort kinda thing `we won't sabotage things'. if you come with faster or slower methods to load customers, no problem. coz noone assumes any.

now take sort. sort says. my input is a range that supports indexing and swapping independent of the range size. if you don't have that just let me know and i'll use a totally different method. just don't pretend.

with that indexing and swapping complexity ain't implementation detail. they're part of the spec. guess stepanov's main contribution was to clarify that.

> For realtime code, I can see the benefit to what you're saying. Although in many cases only part of a program needs to be realtime, and for the rest of the program's code I'd hate to have to sacrifice the encapsulation benefits.

realtime has nothin' to do with it. encapsulation ain't broken by making complexity part of the reqs. any more than any req ain't breakin' encapsulation. if it looks like a problem then encapsulation was misdesigned and needs change.

case in point. all containers should provide 'nth' say is it's o(n) or better. then there's a subclass of container that is indexed_container. that provides opIndex and says it's o(log n) or better. it also provides 'nth' by just forwarding to opIndex. faster than o(n) ain't a problem. but forcing a list to blurt something for opIndex - that's just bad design.
August 26, 2008
"Nick Sabalausky" <a@a.a> wrote in message news:g91m3t$222a$1@digitalmars.com...
> "Jb" <jb@nowhere.com> wrote in message news:g90mm6$2tk9$1@digitalmars.com...
>>
>> "Walter Bright" <newshound1@digitalmars.com> wrote in message news:g90iia$2jc4$3@digitalmars.com...
>>> Yigal Chripun wrote:
>>>> a) people here said that a virtual call will make it slow. How much slow? how much of an overhead is it on modern hardware considering also that this is a place where hardware manufacturers spend time on optimizations?
>>>
>>> Virtual function calls have been a problem for hardware optimization. Direct function calls can be speculatively executed, but not virtual ones, because the hardware cannot predict where it will go. This means virtual calls can be much slower than direct function calls.
>>
>> Modern x86 branch prediction treats indirect calls the same as conditional branches. They get a slot in the branch target buffer, so they do get speculatively executed. And if correctly predicted it's only a couple of cycles more costly direct calls.
>
> Just curious: How "modern", do you mean by "modern" here?

Well I thought it was the Pentium II, but acording to AgnerFog, it's since the PMMX. So pretty much all Pentiums.

Although that's "predict it goes the same place it did last time".

More recent ones do remember multiple targets and recognize some patterns.



August 26, 2008
superdan wrote:
> now take sort. sort says. my input is a range that supports indexing and swapping independent of the range size. if you don't have that just let me know and i'll use a totally different method. just don't pretend.
> 
> with that indexing and swapping complexity ain't implementation detail. they're part of the spec. guess stepanov's main contribution was to clarify that.

The other variable cost operation of a sort is the element comparison. Even if indexing and swapping are O(1), the cost of a comparison between two elements might be O(m), where m is proportional to the size of the elements themselves.

And since a typical sort algorithm will perform n log n comparisons, the cost of the comparison has to be factored into the total cost.

The performance of sorting...say, an array of strings based on a locale-specific collation...could be an expensive operation, if the strings themselves are really long. But that wouldn't make the implementation incorrect, and I'm always glad when a sorting implementation provides a way of passing a custom comparison delegate into the sort routine.

Not a counterargument to what you're saying about performance guarantees for indexing and swapping. Just something else to think about.

--benji
August 26, 2008
"superdan" <super@dan.org> wrote in message news:g91uku$2l93$1@digitalmars.com...
> Benji Smith Wrote:
>
>> superdan wrote:
>> > tho to be brutally honest listenin' more an' talkin' less always helps
>>
>> LOL
>>
>> Coming from you, dan, that's my favorite ironic quote of the day :)
>
> meh. whacha sayin'? i ain't talking much.
Talking, no. Rambling on with a bunch of needless slang, hostility, and missing capitalization that do nothing but hide any kernels of relevance that may or may not exist, yes.


August 26, 2008
"bearophile" <bearophileHUGS@lycos.com> wrote in message news:g91vf8$2mmk$1@digitalmars.com...
> Walter Bright:
>> Looks like I keep falling behind on what modern CPUs are doing :-(
>
> The 5 good PDF files in this page are probably enough to put you back in
> shape:
> http://www.agner.org/optimize/
>
> (Especially ones regarding CPUs and micro architecture. The first document
> is
> the simpler one).

Anger Fog's guides are the best optimization info you can get. They're actualy a lot better than Intels and Amds own optimization guides imo.



August 26, 2008
"Walter Bright" <newshound1@digitalmars.com> wrote in message news:g91kah$1rvb$1@digitalmars.com...
> Jb wrote:
>> Walter said "the hardware cannot predict where a virtual call will go".
>>
>> It does in fact predict them, and speculatively execute them, and as pretty much any bechmark will show it gets it right the vast majority of the time. (On x86 anyway.)
>>
>> That's what I was saying.
>
> Looks like I keep falling behind on what modern CPUs are doing :-(
>
> In any case, throughout all the revolutions in how CPUs work, there have been a few invariants that hold true well enough as an optimization guide:
>
> 1. fewer instructions ==> faster execution
> 2. fewer memory accesses ==> faster execution
> 3. fewer conditional branches ==> faster execution

True. I'd add this to the list aswell..

4. Shorter dependance chains => faster execution.

Although it's more relevant for floating point where most ops have at least a few cycles latency.


August 27, 2008
Nick Sabalausky Wrote:

> "superdan" <super@dan.org> wrote in message news:g91uku$2l93$1@digitalmars.com...
> > Benji Smith Wrote:
> >
> >> superdan wrote:
> >> > tho to be brutally honest listenin' more an' talkin' less always helps
> >>
> >> LOL
> >>
> >> Coming from you, dan, that's my favorite ironic quote of the day :)
> >
> > meh. whacha sayin'? i ain't talking much.
> Talking, no. Rambling on with a bunch of needless slang, hostility, and missing capitalization that do nothing but hide any kernels of relevance that may or may not exist, yes.

don't be hat'n' :)
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19