www.digitalmars.com         C & C++   DMDScript  

D - suggestion: Negative array indexes

reply vb <none nil.com> writes:
As in python:

str="Hello"

[i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
str[i]  :   H  E  L  L  0 H E L L O

of course not only for strings, for all arrays.
Sep 28 2002
next sibling parent reply "Walter" <walter digitalmars.com> writes:
This is a good idea, but it has a significant runtime cost for every array
access.

"vb" <none nil.com> wrote in message
news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
Sep 28 2002
next sibling parent reply "Robert W. Cunningham" <FlyPG users.sourceforge.net> writes:
But that cost should be less than any other way of doing the equivalent
negative indexing.

There are other languages, such as J (think of APL using ASCII, then add
steroids), where negative indexing makes the implementation of many
algorithms far more "natural".  My most recent example was performing some
image manipulation using 3x3 convolution matrices.  There is always the "edge
problem" which in most languages requires lots of special code.  For the
particular problem I was solving, having negative indices "reflect" back into
the matrix provided exactly the solution I needed.

The neat thing about J in this context is that it "knows" about matrices, and
I didn't even have to write a loop.  After defining my matrices, the actual
"code" to do the entire operation was a single line.

If you are going to *really* use arrays, then negative indexing is a great
help.  The alternative is often tons and tons of special-case code, or klugey
things like the following (in C):

  char c = (i >= 0) ? str[i] : str[strlen(str) + i];

Which would become a macro, probably called SIGNED_INDEX().  Which is
something D doesn't really want to have.  And this is something the compiler
does better anyhow.


-BobC


Walter wrote:

 This is a good idea, but it has a significant runtime cost for every array
 access.

 "vb" <none nil.com> wrote in message
 news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
Sep 28 2002
next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
I also like negative indexing.  Icon supports it too.

I encountered the "edge problem" in my image processing work and negative
indices help a lot in many algorithm domains.

Mark
Sep 28 2002
parent reply "Mike Wynn" <mike.wynn l8night.co.uk> writes:
I also like the python, perl way of allowing -ve array offset to mean "from
the end"
BUT this changes the points at which you get an "out of bounds" exception
from
index < 0  and index >= array.length to  index < -array.length and index >=
array.length
meaning that if there was a bug in your code you would get junk data instead
of a exception

I would prefer a syntax like
array:wrap[idx]  (-ve is from end, +ve as usual : bounds checked)
and
array:ring[idx]  (idx % array.length so never throws an exception)

Mike.

"Mark Evans" <Mark_member pathlink.com> wrote in message
news:an52r2$2jnd$1 digitaldaemon.com...
 I also like negative indexing.  Icon supports it too.

 I encountered the "edge problem" in my image processing work and negative
 indices help a lot in many algorithm domains.

 Mark
Sep 28 2002
next sibling parent Mark Evans <Mark_member pathlink.com> writes:
I don't follow you.  Negative indices have boundaries too, and if the positive
equivalent throws an exception, then so should the negative.

I like the idea of a ring index -- and will do it one better.  In image
processing one often likes to mirror the edges to achive smoothness.  An
out-of-bounds index reflects back into the original array.  The alternative of
zero-padding introduces a severe discontinuity.

I'm not sure which, if any, of our combined features actually belong in the core
language, but negative indexing does.  That makes all the other things easier to
implement.

Mark
Sep 28 2002
prev sibling parent reply Mac Reiter <Mac_member pathlink.com> writes:
In article <an59h5$2ptq$1 digitaldaemon.com>, Mike Wynn says...
I would prefer a syntax like
array:wrap[idx]  (-ve is from end, +ve as usual : bounds checked)
and
array:ring[idx]  (idx % array.length so never throws an exception)

Mike.
And a hearty second for that! The performance problem with allowing negative indices on unadorned arrays is that you take the performance hit on every array index, even for arrays that you know are never going to be negatively indexed. I really like the wrap/ring idea, because it lets normal arrays be accessed at full speed, and special case arrays be treated as special case arrays. Dunno about the syntax. Works well enough for me, but I could also see "building it in" to arrays, kind of like reverse(): array.wrap()[idx] array.ring()[idx] or array.wrap(idx) array.ring(idx) I have to admit that I prefer your syntax over mine, but thought I'd throw it out there in case it had any consistency or parsing benefits that might outweigh the aesthetic problems... Mac
Sep 30 2002
parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Mac Reiter" <Mac_member pathlink.com> wrote in message
news:an9mu2$17at$1 digitaldaemon.com...
 In article <an59h5$2ptq$1 digitaldaemon.com>, Mike Wynn says...
I would prefer a syntax like
array:wrap[idx]  (-ve is from end, +ve as usual : bounds checked)
and
array:ring[idx]  (idx % array.length so never throws an exception)

Mike.
And a hearty second for that! The performance problem with allowing
negative
 indices on unadorned arrays is that you take the performance hit on every
array
 index, even for arrays that you know are never going to be negatively
indexed.
 I really like the wrap/ring idea, because it lets normal arrays be
accessed at
 full speed, and special case arrays be treated as special case arrays.

 Dunno about the syntax.  Works well enough for me, but I could also see
 "building it in" to arrays, kind of like reverse():

 array.wrap()[idx]
 array.ring()[idx]

 or
 array.wrap(idx)
 array.ring(idx)
Fine. This fits better into the property syntax. And we could also have: array.checked(idx) Which would not do wrapping, but bounds checking in both directions. Sandor
Sep 30 2002
parent reply Mark Evans <Mark_member pathlink.com> writes:
I will buy into the idea of an extra property for fancy indexing.  That sounds
good.  I myself was considering a new D type ("buffer"?) but it makes more sense
to add array properties.

I understand where Walter is coming from.  It is true that C++ has an
underserved rap sheet on the performance issue.

My own view of the language world is a little different from Walter's.  I see no
need for a new language built around screaming performance as its (a) number one
design priority, (b) main user attraction, and (c) chief evaluation criterion.
We already have C, C++, and assembly for that, and D can link to them.

I see a need for a compiled language midway between C++ and script languages.  I
would consider it fine if D were on a par with C++ in most performance
categories, while higher in some and lower in others.  To my mind there is no
requirement to beat C++ in every single category.  I do see Mac's point that it
is better not to be forced into lower performance if a choice can be provided.
Neither should I be forced into higher performance if it means algorithms take
5-10 times longer to write and debug.

Having said that, no one has yet convinced me that this negative index trick is
a real killer anyway, but think the proposed compromises are on the right track.
In Icon for example, I can easily write code that performs just as fast as
equivalent C, negative indices and all.  The difference is the time it takes to
write the program correctly.  Icon is a breeze and C is a pain.

I agree with Walter that #pragmas and compiler switches are ugly. It's just that
I view this whole performance orientation as servicing such a narrow audience
that it almost merits such ugliness.  D will perform well enough for most work
-- better than all (interpreted) script languages and practically par with C.
The language acceptance factor will revolve around: what it is good for? how
easy is it to use? what can it do that C++ can't? can it get the job done
faster? and so on.  Performance will matter too, but it is not going to be the
show-stopper.  D needs much, much more than that to win a place for itself.

It might be worth considering how many languages have fallen by the wayside and
what caused them to do so.  Icon is an example -- a very beautiful language with
no market presence.  One sees an ugly creature like Visual Basic which, for all
its performance problems, has a huge market presence and almost outstrips C++
itself.  So there is more to language acceptance than performance or even
elegance.  In the VB case the answer is "easy to use" and that factor is greatly
enhanced by the sort of features we are debating here.

Mark
Oct 01 2002
parent reply "Walter" <walter digitalmars.com> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:and4mr$27aq$1 digitaldaemon.com...
 My own view of the language world is a little different from Walter's.  I
see no
 need for a new language built around screaming performance as its (a)
number one
 design priority, (b) main user attraction, and (c) chief evaluation
criterion.
 We already have C, C++, and assembly for that, and D can link to them.
Performance is a high priority, but for D it does not trump everything else. For example, in D all functions are virtual, which will cost some very slight performance compared with an expertly crafted C++ program, but for the relief from bugs and for real programs, it's worth it. D also loses some performance by not allowing class objects on the stack, but the huge gains are worth it.
 I see a need for a compiled language midway between C++ and script
languages. I
 would consider it fine if D were on a par with C++ in most performance
 categories, while higher in some and lower in others.  To my mind there is
no
 requirement to beat C++ in every single category.  I do see Mac's point
that it
 is better not to be forced into lower performance if a choice can be
provided.
 Neither should I be forced into higher performance if it means algorithms
take
 5-10 times longer to write and debug.
D does the dhrystone benchmark faster than C <g>.
 I agree with Walter that #pragmas and compiler switches are ugly. It's
just that
 I view this whole performance orientation as servicing such a narrow
audience
 that it almost merits such ugliness.  D will perform well enough for most
work
 -- better than all (interpreted) script languages and practically par with
C.
 The language acceptance factor will revolve around: what it is good for?
how
 easy is it to use? what can it do that C++ can't? can it get the job done
 faster? and so on.  Performance will matter too, but it is not going to be
the
 show-stopper.  D needs much, much more than that to win a place for
itself. I believe D has that. I've gone well past the point where I keep finding myself frustrated when doing a bit of C++, because it's much easier to get it done, right, and tested in D.
 It might be worth considering how many languages have fallen by the
wayside and
 what caused them to do so.  Icon is an example -- a very beautiful
language with
 no market presence.
I have no idea why Icon failed. It's a remarkable language. I have the manual for it now and the implementation book <g>.
  One sees an ugly creature like Visual Basic which, for all
 its performance problems, has a huge market presence and almost outstrips
C++
 itself.  So there is more to language acceptance than performance or even
 elegance.  In the VB case the answer is "easy to use" and that factor is
greatly
 enhanced by the sort of features we are debating here.
Basic is a fine language if your program is less than 24 lines long. I don't see it as a competitor for C++ or D, it serves a completely different need. Even if VB vanished tomiorrow, VB programmers won't switch to C++. They'll switch to javascript, Perl, Python or something similar.
Oct 01 2002
next sibling parent "Roberto Mariottini" <rmariottini lycosmail.com> writes:
"Walter" <walter digitalmars.com> ha scritto nel messaggio
news:ane4kc$5fv$1 digitaldaemon.com...
[...]

 Basic is a fine language if your program is less than 24 lines long. I
don't
 see it as a competitor for C++ or D, it serves a completely different
need.
 Even if VB vanished tomiorrow, VB programmers won't switch to C++. They'll
 switch to javascript, Perl, Python or something similar.
I think Delphi has a point here: simple, fast, powerful and portable. Do you think D will have a little slice of them? Ciao
Oct 02 2002
prev sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
Performance is a high priority, but for D it does not trump everything else.
For example, in D all functions are virtual
Good, good.
 I see a need for a compiled language midway between C++ and script
D does the dhrystone benchmark faster than C <g>.
Yes, but does it take less time to *write* the benchmark in D? That is the kind of question performance benchmarks can never answer.
I believe D has that. I've gone well past the point where I keep finding
myself frustrated when doing a bit of C++, because it's much easier to get
it done, right, and tested in D.
D as it stands is better than C++, but is still much too close to C and much too far from script langugaes. I haven't used D enough to make fair statements. I have used negative indexing enough to make opinionated statements about that :-).
I have no idea why Icon failed. It's a remarkable language. I have the
manual for it now and the implementation book <g>.
The point was that D might suffer a similar fate. I have some guesses about Icon. Lack of open-source development (until very recently), lack of marketing (comparison/contrast articles), lack of serious GUI tools, bad luck.
Basic is a fine language if your program is less than 24 lines long. I don't
see it as a competitor for C++ or D, it serves a completely different need.
Even if VB vanished tomiorrow, VB programmers won't switch to C++. They'll
switch to javascript, Perl, Python or something similar.
You missed my point completely here. The point was that Visual Basic fails catastrophically on all benchmark performance tests, yet conquered the market. The fact that VB users would switch to Python, not C++, only proves the point more emphatically: performance is not the trump suit. It does not prove that they serve different needs at all. People are doing a lot more with VB than writing 24-line programs. Serious, real-world programs are written with VB all day long, and people make good money doing it. That is the kind of outcome I would like for D. All of these VB programs could instead be written in C++. My point was that performance is only one factor in market acceptance, and VB proves it is not necessarily a major one. Ease of use is much higher on the list. VB and C++ do not really serve different needs; VB edged out C++ in several problem domains because it is easier to use. I'd also point out that Microsoft (no dummy at marketing) has recognized the success of VB-like tools sense. So when a proposed feature only costs 5-10%, but yields 3x algorithm design gains, I say that it is worth it. If I want extreme performance, and have all day long to tweak and tune, then I will extern-C the thing and suffer the consequences. Nice chatting Walter...and D is still fabulous, Mark
Oct 02 2002
next sibling parent reply "chris jones" <flak clara.co.uk> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:anf85d$1c99$1 digitaldaemon.com...
Basic is a fine language if your program is less than 24 lines long. I
don't
see it as a competitor for C++ or D, it serves a completely different
need.
Even if VB vanished tomiorrow, VB programmers won't switch to C++.
They'll
switch to javascript, Perl, Python or something similar.
You missed my point completely here. The point was that Visual Basic
fails
 catastrophically on all benchmark performance tests, yet conquered the
market. D is meant to be a sucessor to C++ not VB, so whether D is fast enough for people using VB is irelevant, what is important is whether it is fast enough to attract people using C++.
 The fact that VB users would switch to Python, not C++, only proves the
point
 more emphatically:  performance is not the trump suit.  It does not prove
that
 they serve different needs at all.
Your argument is like saying 'some people walk to work so therefore most people dont care how long it takes otherwise they would be in cars!' All you prove is that VBers car little about speed, not progranmers in general. There are even some of us still using assembler ;) Speed is important to many people. chris
Oct 04 2002
next sibling parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
I rewrote two functions in assembler yesterday for PS2 VU0.  :)  Got down to
only taking about half the time pretty easily.

When you do need performance, you absolutely do need it.  Having to resort
to extern "C" or asm isn't a good solution and should be reserved for last
resort.  That means D should be pretty damn fast by default.  If some
language feature is going to sac performance it should be avoidable.  Right
now you can avoid virtual function call overhead (if you use structs or
global functions).  You should be able to avoid negative index checking.

Sean

"chris jones" <flak clara.co.uk> wrote in message
news:ankh38$t5e$1 digitaldaemon.com...
 Your argument is like saying 'some people walk to work so therefore most
 people dont care how long it takes otherwise they would be in cars!' All
you
 prove is that VBers car little about speed, not progranmers in general.
 There are even some of us still using assembler ;) Speed is important to
 many people.

 chris
Oct 04 2002
prev sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
Hi Chris and Sean!


Chris wrote:
 D is meant to be a sucessor to C++ not VB, so whether D is fast enough for
 people using VB is irelevant, what is important is whether it is fast enough
 to attract people using C++.
I did not say that D is an heir to VB. I said that if D wants to succeed in the marketplace, then certain issues come into play, and VB offers important lessons about those issues. Chris wrote:
 Your argument is like saying 'some people walk to work so therefore most
 people dont care how long it takes otherwise they would be in cars!' All you
 prove is that VBers car little about speed, not progranmers in general.
No. The success of VB shows that lots of "programmers in general" -- not just "some" -- consider other things than speed in selecting a language. This fact is easy to quantify. Monster.com is one of the top job boards in the nation. Keyword "Visual Basic" yields 2853 jobs, while "C++" yields 2543 jobs. That is better than 1:1 in favor of VB. Sean wrote:
 When you do need performance, you absolutely do need it.  Having to resort
 to extern "C" or asm isn't a good solution
I call your five and raise you five: when you absolutely need to finish a project, you absolutely need the language features to finish it. Regards- Mark
Oct 04 2002
parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
You are right.  Just try not to unnecessarily degrade global program
performance ala SEH.  ;)

Sean

"Mark Evans" <Mark_member pathlink.com> wrote in message
news:anlu5i$2aa4$1 digitaldaemon.com...
 Sean wrote:
 When you do need performance, you absolutely do need it.  Having to
resort
 to extern "C" or asm isn't a good solution
I call your five and raise you five: when you absolutely need to finish a project, you absolutely need the language features to finish it. Regards- Mark
Oct 05 2002
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:anf85d$1c99$1 digitaldaemon.com...
 People are doing a lot more with VB than writing 24-line programs.
Serious,
 real-world programs are written with VB all day long, and people make good
money
 doing it.
Of course you're right. What I think happens is that people get sucked into VB because it's so easy to write 24 line programs in it, and just keep extending things from Inertia. The larger a program is the more important the organizational abilities of the language become. VB doesn't offer much of that. I think it takes a far better programmer to make a 30000 line VB program work than a 30000 line C++ program. And I think it takes a far better programmer to make a 30000 line C++ program work than a 30000 line D program (even including the fact that D can represent the same algorithm with a lot fewer lines of code).
Oct 05 2002
parent reply Mark Evans <Mark_member pathlink.com> writes:
What I think happens is that people get sucked into
VB because it's so easy to write 24 line programs in it, and just keep
extending things from Inertia
It's easy to write 24 line program in any language. My VB developer friends also know C++, but use VB for its RAD qualities -- the ability to write quickly something large enough to do useful work. From their viewpoint it's actually the larger programs that matter, not the 24-line toys. I hope that D can manage to attract VB programmers as well as C++ programmers. It's also worth remembering that C++ hasn't won any language design beauty contests, either. Mark
Oct 05 2002
parent "Walter" <walter digitalmars.com> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:ano8se$2edq$1 digitaldaemon.com...
 I hope that D can manage to attract VB programmers as well as C++
programmers. That would be possible only if some VB-like RAD environment was added.
 It's also worth remembering that C++ hasn't won any language design beauty
 contests, either.
I find any non-trivial C++ template code to be very hard to examine, which was a big motivator to try and come up with a better syntax for D.
Oct 08 2002
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
Negative indexing will require an extra test for every array reference. That
will put it behind in any efficiency comparisons with C++.


The alternative is often tons and tons of special-case code, or klugey
 things like the following (in C):

   char c = (i >= 0) ? str[i] : str[strlen(str) + i];
In D it would be: char c = (i >= 0) ? str[i] : str[str.length + i]; You could do it with an inline function: char index(str, int i) { return (i >= 0) ? str[i] : str[str.length + i]; }
Sep 28 2002
next sibling parent reply "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
Don't give in, Walter.  Negative indices are nifty and all, but definitely
not worth the performance loss.

Sean

"Walter" <walter digitalmars.com> wrote in message
news:an66dr$jok$1 digitaldaemon.com...
 Negative indexing will require an extra test for every array reference.
That
 will put it behind in any efficiency comparisons with C++.
Sep 29 2002
parent "Walter" <walter digitalmars.com> writes:
I agree. Fundamental Performance is crucial to D or people will not upgrade
from C++.

"Sean L. Palmer" <seanpalmer directvinternet.com> wrote in message
news:an6ad2$q8c$1 digitaldaemon.com...
 Don't give in, Walter.  Negative indices are nifty and all, but definitely
 not worth the performance loss.

 Sean

 "Walter" <walter digitalmars.com> wrote in message
 news:an66dr$jok$1 digitaldaemon.com...
 Negative indexing will require an extra test for every array reference.
That
 will put it behind in any efficiency comparisons with C++.
Sep 29 2002
prev sibling next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
The concern over performance is valid but:

- Unsigned integers require no test at all, so a different object code gen
subroutine could be invoked for them

- The kind of performance worry under consideration is one of those
that matters only to serious numerical analysts and database engineers,
who are working with fairly large data sets, not everyday programming;
even with the extra test, my bet is that performance won't suffer more
than 5%-10% in typical algorithms

- The gains are huge with negative indices in algorithm design, and most
software managers glady sacrifice performance to "get the job done";
that is where D must really shine, not inner loop performance;
I've *never* had a manager complement me on inner loop performance,
but they *always* want to know "when will the project be done" and
D must convince managers of its usefulness in answering that question

- A #pragma-like directive or compiler switch is always possible to scope
sections of code that should assume positive indices only

- One of the great features of C++, with which D must compete, is STL; and
STL offers backward iterators

- One of the great features of script languages (including MATLAB, IDL, and
Mathematica along with Icon/Perl/Python families) is their facility with
manipulating data in ways that C/C++ cannot, and the more of those features
are available in D, the better; I do not view C/C++ as any kind of model
language in terms of data manipulation, and that by itself has driven many
people away from C++ even though performance is lower; again, the
"get it done" factor outweighs inner loop performance almost every time,
and when inner loop performance becomes a concern, it will merit its own
engineering effort

- Negative indices have a direct influence on the design of circular buffers
which were mentioned in a previous post

- Thanks everyone for an interesting discussion and to Walter

Mark


In article <an66dr$jok$1 digitaldaemon.com>, Walter says...
Negative indexing will require an extra test for every array reference. That
will put it behind in any efficiency comparisons with C++.


The alternative is often tons and tons of special-case code, or klugey
 things like the following (in C):

   char c = (i >= 0) ? str[i] : str[strlen(str) + i];
In D it would be: char c = (i >= 0) ? str[i] : str[str.length + i]; You could do it with an inline function: char index(str, int i) { return (i >= 0) ? str[i] : str[str.length + i]; }
Sep 29 2002
parent "Walter" <walter digitalmars.com> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:an7uj7$2dpn$1 digitaldaemon.com...
 The concern over performance is valid but:

 - Unsigned integers require no test at all, so a different object code gen
 subroutine could be invoked for them
Yes, that could work, but couldn't the subtly different behavior be pretty confusing?
 - The kind of performance worry under consideration is one of those
 that matters only to serious numerical analysts and database engineers,
 who are working with fairly large data sets, not everyday programming;
 even with the extra test, my bet is that performance won't suffer more
 than 5%-10% in typical algorithms
5-10% is probably accurate, but it doesn't take too many of those to kill the performance. Nobody expects Icon or Python to execute fast, but people will expect D to.
 - The gains are huge with negative indices in algorithm design, and most
 software managers glady sacrifice performance to "get the job done";
 that is where D must really shine, not inner loop performance;
 I've *never* had a manager complement me on inner loop performance,
 but they *always* want to know "when will the project be done" and
 D must convince managers of its usefulness in answering that question
I write a lot of system code, and I have had acceptance held up until that last 10% of speed was achieved. I've seen a lot of (inaccurate) dissing of C++ as being slower than C; the last thing D needs is the convenient excuse for not using it because it is irredeemably slower than C++.
 - A #pragma-like directive or compiler switch is always possible to scope
 sections of code that should assume positive indices only
That will work, but forgive me, down that path lies madness <g>.
 - One of the great features of C++, with which D must compete, is STL; and
 STL offers backward iterators
The STL iterator issue is important, and I have some ideas for addressing it.
 - One of the great features of script languages (including MATLAB, IDL,
and
 Mathematica along with Icon/Perl/Python families) is their facility with
 manipulating data in ways that C/C++ cannot, and the more of those
features
 are available in D, the better; I do not view C/C++ as any kind of model
 language in terms of data manipulation, and that by itself has driven many
 people away from C++ even though performance is lower; again, the
 "get it done" factor outweighs inner loop performance almost every time,
 and when inner loop performance becomes a concern, it will merit its own
 engineering effort
But the people D needs to attract are those people who want performance in their language.
 - Negative indices have a direct influence on the design of circular
buffers
 which were mentioned in a previous post
Yes. But you can always make it work by designing an inline function.
 - Thanks everyone for an interesting discussion and to Walter
Yes, it is a great discussion and your ideas are valuable. I do especially appreciate reading your well thought out arguments for them.
Sep 29 2002
prev sibling parent reply Mac Reiter <Mac_member pathlink.com> writes:
In article <an66dr$jok$1 digitaldaemon.com>, Walter says...
Negative indexing will require an extra test for every array reference. That
will put it behind in any efficiency comparisons with C++.


The alternative is often tons and tons of special-case code, or klugey
 things like the following (in C):

   char c = (i >= 0) ? str[i] : str[strlen(str) + i];
In D it would be: char c = (i >= 0) ? str[i] : str[str.length + i]; You could do it with an inline function: char index(str, int i) { return (i >= 0) ? str[i] : str[str.length + i]; }
And since arrays know their length at all times, D's str.length is 'length' times faster than C's strlen(str), which had to do a linear traversal looking for the NULL. That makes the D version not just a syntactic difference, but a very real performance improvement. Mac
Sep 30 2002
parent "Walter" <walter digitalmars.com> writes:
"Mac Reiter" <Mac_member pathlink.com> wrote in message
news:an9o61$18j0$1 digitaldaemon.com...
 And since arrays know their length at all times, D's str.length is
'length'
 times faster than C's strlen(str), which had to do a linear traversal
looking
 for the NULL.  That makes the D version not just a syntactic difference,
but a
 very real performance improvement.
Yup. That's one of the reasons why D programs can run faster than C.
Oct 01 2002
prev sibling parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Walter" <walter digitalmars.com> wrote in message
news:an4pt6$2b0o$1 digitaldaemon.com...
 This is a good idea, but it has a significant runtime cost for every array
 access.

 "vb" <none nil.com> wrote in message
 news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
That kind of runtime cost is not affordable. BUT: What if this "symmetric" indexing is done through a separate property? The [] operator remains the same, and you invent a new property such as: char a = str.at(i); This new property would do symmetric indexing, and ... well ... upper bounds checking? I think this combination would result in maximum runtime performance. If we don't have the opportunity to build own dynamic array types (lack of [] operator overload), then the built-in array type should be feature-rich. Yours, Sandor
Sep 30 2002
parent reply "Les Baker" <REMOVETHISlesbaker innova.netREMOVETHIS> writes:
 What if this "symmetric" indexing is done through a separate property?
 The [] operator remains the same, and you invent a new property such as:

 char a = str.at(i);
I second this. Just three more characters than a normal array access.
 This new property would do symmetric indexing, and ... well ... upper
bounds
 checking?
I kinda thought the "ring" property was neat too, but I don't know how that would fit into this scheme (would "at" do that kind of access? probably not...). I do think that this is great; C++'s vector does this same thing, its [] operator is direct access and its .at() function is exactly like this. It's a clear bonus for D because C++ would be using the same syntax, and Walter seems concerned about attracting & transitioning those users to D, so those users would be immediately comfortable with this syntax.
 I think this combination would result in maximum runtime performance.
 If we don't have the opportunity to build own dynamic array types (lack of
 [] operator overload),
 then the built-in array type should be feature-rich.
Since the basic array type cannot be overloaded (and that's kinda good in a way for consistency, but bad for extending it), I think that is why everyone is concerned about the built in array type(s) being just right; it has to be "good enough" for 99.5% of situations, and I don't see a STL for D coming along (for that 0.5% of code) unless D gets really popular. Now a question: according to the "Memory Model" document, dynamic arrays have their first dword pointing to the start of the data, so (for example) an array located in memory at 0xF0000000 would have as its first four bytes 0xF0000008. When doing an array access why can't it be *assumed* that the array data starts eight bytes into the array. So say you coded "aNumber = myIntegers[5];", then the value at (pointer to array) + (element number * type scalar + 8 bytes) would be accessed. Then the unused first four bytes could be used for other things. I know there's probably a good reason for the current setup, I just don't know what it is, or I could be missing something entirely.
Sep 30 2002
next sibling parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
float[4] myvec;
myvec.at[-1] = 3; myvec.at[-2] = 2; myvec.at[-3] = 1; myvec.at[-4] = 0;
printf("%f%f%f%f\n",myvec[0],myvec[1],myvec[2],myvec.at[3]);

prints 0123

I think it would be cool to be able to override a local [] operator for any
container type (any class that has an [] operator itself) for any index
type, implement it, and call it with normal array index syntax with values
of the right types.

I know this isn't D but it's not C++ either:

int& float[]::operator[int x]  // reverses any float[] arrays in this scope.
{
    return super[super.size() - 1 - x];
}

void foo()
{
    float[2] x = {0,1};
    print x[0];   // writes 1
    print x[1];   // writes 0
}

Fun huh?  Reversing arrays is no good obviously but you could do a hash map
or something.

With templates that could end up being really powerful.  A suite of data
connector tools, when taken to extremes.  Everything from straight pipes to
compressors to translators to reindexers to databases to RPC to whatever.

Just think what your compiler could do if it had access to a teensy compiler
at runtime.  It could choose from several algorithms depending on how
efficient they are at handling recent data.  It could choose between random
access and searches and brute force linear traversal with varying sizes in
mind (i.e. exploit SIMD to unroll loops).  Every once in a while it tries
new algorithms in different spots in the program and sees which ones are
handling the data flow most efficiently on the target platform.  .net could
become this kind of backend.  I suppose gcc might could do this.  Alot of
that could be done statically.

Sean

"Les Baker" <REMOVETHISlesbaker innova.netREMOVETHIS> wrote in message
news:anaoor$2ejr$1 digitaldaemon.com...
 What if this "symmetric" indexing is done through a separate property?
 The [] operator remains the same, and you invent a new property such as:

 char a = str.at(i);
I second this. Just three more characters than a normal array access.
 This new property would do symmetric indexing, and ... well ... upper
bounds
 checking?
I kinda thought the "ring" property was neat too, but I don't know how
that
 would fit into this scheme (would "at" do that kind of access? probably
 not...). I do think that this is great; C++'s vector does this same thing,
 its [] operator is direct access and its .at() function is exactly like
 this. It's a clear bonus for D because C++ would be using the same syntax,
 and Walter seems concerned about attracting & transitioning those users to
 D, so those users would be immediately comfortable with this syntax.

 I think this combination would result in maximum runtime performance.
 If we don't have the opportunity to build own dynamic array types (lack
of
 [] operator overload),
 then the built-in array type should be feature-rich.
Since the basic array type cannot be overloaded (and that's kinda good in
a
 way for consistency, but bad for extending it), I think that is why
everyone
 is concerned about the built in array type(s) being just right; it has to
be
 "good enough" for 99.5% of situations, and I don't see a STL for D coming
 along (for that 0.5% of code) unless D gets really popular.

 Now a question: according to the "Memory Model" document, dynamic arrays
 have their first dword pointing to the start of the data, so (for example)
 an array located in memory at 0xF0000000 would have as its first four
bytes
 0xF0000008. When doing an array access why can't it be *assumed* that the
 array data starts eight bytes into the array. So say you coded "aNumber =
 myIntegers[5];", then the value at (pointer to array) + (element number *
 type scalar + 8 bytes) would be accessed. Then the unused first four bytes
 could be used for other things. I know there's probably a good reason for
 the current setup, I just don't know what it is, or I could be missing
 something entirely.
Sep 30 2002
prev sibling parent Burton Radons <loth users.sourceforge.net> writes:
Les Baker wrote:
What if this "symmetric" indexing is done through a separate property?
The [] operator remains the same, and you invent a new property such as:

char a = str.at(i);
I second this. Just three more characters than a normal array access.
This new property would do symmetric indexing, and ... well ... upper
bounds
checking?
I kinda thought the "ring" property was neat too, but I don't know how that would fit into this scheme (would "at" do that kind of access? probably not...). I do think that this is great; C++'s vector does this same thing, its [] operator is direct access and its .at() function is exactly like this. It's a clear bonus for D because C++ would be using the same syntax, and Walter seems concerned about attracting & transitioning those users to D, so those users would be immediately comfortable with this syntax.
A negative indexing method should still do bounds checking, so .at and .ring would have different semantics. I can see the methods as being: a.at (x) = a [x < 0 ? x + a.length : x]; a.ring (x) = a [((x % a.length) + a.length) % a.length]; a.saturate (x, y) = a [x < 0 ? y : x >= a.length ? y : a [x]) a.mirror (x) = bloody complex
I think this combination would result in maximum runtime performance.
If we don't have the opportunity to build own dynamic array types (lack of
[] operator overload),
then the built-in array type should be feature-rich.
Since the basic array type cannot be overloaded (and that's kinda good in a way for consistency, but bad for extending it), I think that is why everyone is concerned about the built in array type(s) being just right; it has to be "good enough" for 99.5% of situations, and I don't see a STL for D coming along (for that 0.5% of code) unless D gets really popular.
Then I hope D never becomes popular. :-)
 Now a question: according to the "Memory Model" document, dynamic arrays
 have their first dword pointing to the start of the data, so (for example)
 an array located in memory at 0xF0000000 would have as its first four bytes
 0xF0000008. When doing an array access why can't it be *assumed* that the
 array data starts eight bytes into the array. So say you coded "aNumber =
 myIntegers[5];", then the value at (pointer to array) + (element number *
 type scalar + 8 bytes) would be accessed. Then the unused first four bytes
 could be used for other things. I know there's probably a good reason for
 the current setup, I just don't know what it is, or I could be missing
 something entirely.
The memory model page is wrong; it should distinguish between stack objects and heap objects. Arrays are stack objects that take eight bytes, a length and then a data pointer (in the opposite order to the memory model page); the data they point to are just a flat array with no information. If any data were stored in the array you wouldn't be able to do slicing.
Oct 02 2002
prev sibling next sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
vb wrote:

 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
*IF* (that's a big if) the optimizer was smart enough, you could use the syntax: str.reverse[n] to access the n'th element from the end. So your characters would be: reverse[4] H reverse[3] E reverse[2] L reverse[1] L reverse[0] O [0] H [1] E [2] L [3] L [4] O -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]
Sep 28 2002
prev sibling next sibling parent reply "chris jones" <flak clara.co.uk> writes:
Whats wrong with using

str[(i + str.length) mod str.length];

or if you want more that one wrap of negative indexing use

str[(i + (x * str.length)) mod str.length];

where x denotes how many times round negative you need to go.

I think this it is only going to be off use to a minority of people and
should be coded when they need it. Also if you are doing convolution as has
been sugested it would realy slow the perfomance very severly, at least
100%.  I definatly would not use it because of that and the fact that its
little (if not none) use in audio dsp.

chris


"vb" <none nil.com> wrote in message
news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
Sep 29 2002
parent reply Mark Evans <Mark_member pathlink.com> writes:
Chris,

This whole area of array manipulation is one of the huge, gaping holes in C/C++
that any replacement language should strive to fix.  I categorically disagree
that array (and by extension, string) manipulation is some kind of obscure
backwater.

If you focus attention on numerical routines like convolution then you can
probably isolate cases where negative indices cause a real performance hit.  So
what.  My experience teaches that coding correctly and quickly is vastly more
important.  Performance issues always take a back seat.  I say to you about
extreme performance just what you say to me about negative indexing: it's only
helpful to a small minority who should be hand-coding anyway.

I've written literally dozens of convolution routines (1D and 2D) using C and
also using script languages.  The first thing I did was to construct a "negative
index" system to facilitate the convolution algorithms.  In some languages that
was not necessary because it was already built-in.  Guess which languages I
preferred?  I would have been in heaven if my C compiler had supported negative
indices.

I've also used negative indexing extensively in Icon string processing and  it
is a real blessing.  (Consider right-to-left languages, among other things.)  I
swear, one of these days I am going to port Icon to C, just so I can have its
string processing power in C.

I am beginning to wonder how D will become "a better C++" if nobody wants
non-C++ features in the language!

Mark


In article <an88kh$2nc1$1 digitaldaemon.com>, chris jones says...
Whats wrong with using

str[(i + str.length) mod str.length];

or if you want more that one wrap of negative indexing use

str[(i + (x * str.length)) mod str.length];

where x denotes how many times round negative you need to go.

I think this it is only going to be off use to a minority of people and
should be coded when they need it. Also if you are doing convolution as has
been sugested it would realy slow the perfomance very severly, at least
100%.  I definatly would not use it because of that and the fact that its
little (if not none) use in audio dsp.

chris


"vb" <none nil.com> wrote in message
news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
Sep 29 2002
next sibling parent "chris jones" <flak clara.co.uk> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:an8chi$2qp4$1 digitaldaemon.com...
 Chris,

 This whole area of array manipulation is one of the huge, gaping holes in
C/C++
 that any replacement language should strive to fix.  I categorically
disagree
 that array (and by extension, string) manipulation is some kind of obscure
 backwater.
I can see why it is desirable but i have only needed it a couple of times in the last few so i guese its of little importance to me.
 If you focus attention on numerical routines like convolution then you can
 probably isolate cases where negative indices cause a real performance
hit. So
 what.  My experience teaches that coding correctly and quickly is vastly
more
 important.  Performance issues always take a back seat.  I say to you
about
 extreme performance just what you say to me about negative indexing: it's
only
 helpful to a small minority who should be hand-coding anyway.
It would cause a severe performance hit in every instance of convolution. If every array index now takes twice as long that is unaceptable for most dsp programers i know, the same people who probably would benefit from negative indexing would also be very unhapy with the performance hit. Also if it was built into the language it would have to be more robust and would be even slower you couldn't asume a minumun negative wrap round and hence it would take more than the extra 3 arithmetic ops, mabey even a jmp, arrgh. I get a significant perfomance increase when i turn the bounds checking of in delphi so i guese negative indexing would be the same, if not more, i think its 4 ops for bounds checking in delphi. Actualy what i would like - and negative indexing could be an extension to this idea - is to be able to specify when accesing the array whether you want bounds checking. Nagative indexing could be an option but i do not want to be forced to use it. I dont know what good syntax would be, definatly not like this but the idea is.... str[i] bounds checked no negative indexing str![i] no bounds checking str-[i] negative indexed
 I've written literally dozens of convolution routines (1D and 2D) using C
and
 also using script languages.  The first thing I did was to construct a
"negative
 index" system to facilitate the convolution algorithms.  In some languages
that
 was not necessary because it was already built-in.  Guess which languages
I
 preferred?  I would have been in heaven if my C compiler had supported
negative
 indices.
What is so hard about the method i sugested?
 I've also used negative indexing extensively in Icon string processing and
it
 is a real blessing.  (Consider right-to-left languages, among other
things.) I
 swear, one of these days I am going to port Icon to C, just so I can have
its
 string processing power in C.

 I am beginning to wonder how D will become "a better C++" if nobody wants
 non-C++ features in the language!
I though part of the idea was to keep a small feature set to ovoid the Bloat++. Actualy i think D is shapping up to be an exelent language but in that it cant also be all things to all people. chris
Sep 30 2002
prev sibling next sibling parent reply Mac Reiter <Mac_member pathlink.com> writes:
In article <an8chi$2qp4$1 digitaldaemon.com>, Mark Evans says...
Chris,

If you focus attention on numerical routines like convolution then you can
probably isolate cases where negative indices cause a real performance hit.  So
what.  My experience teaches that coding correctly and quickly is vastly more
important.  Performance issues always take a back seat.  I say to you about
extreme performance just what you say to me about negative indexing: it's only
helpful to a small minority who should be hand-coding anyway.

Mark
One of the problems I have with "ease of programming" over performance is that if I have a language that provides performance, I can make inline functions to provide functionality. But if my language forces the functionality on me at the expense of performance, I cannot get the performance back without resorting to a lower level language. I have had the misfortune to do graphics programming and manipulation in VB. While the array checks in that language did make it much easier to debug my program, turning them off made a 200%-300% difference in runtime. When the application is a special effects video editing tool that has to process hundreds of thousands of images, it is impossible to say "but it was so much easier to write the slow version" and get any kind of user sympathy. (And for what it is worth, with the various array checks turned off, the compiled VB program did end up very close to as fast as a compiled C app would be -- both languages use the same back end compiler and optimizer, and the "pure" math and memory access I was using was indistinguishable between the languages) Don't get me wrong -- I like functionality in languages. I like having stuff built-in that makes my life easier. That's why I seconded the vote for a "decoration" syntax that would mark certain array accesses as being wrapped (reflected?) or ringed, without imposing that penalty on unadorned arrays. I also think that my alternate syntax, with wrap() and ring() functions built into the array system is not horrible. If such functions are built in, the compiler knows what they do and can apply any special optimizations the implementor can conceive of inside those accesses. It also provides the benefit of flagging those uses to the human who has to read and maintain the code. As a long time C/C++/Fortan/VB/Ada/etc programmer, my first reaction to "array[-2]" is that I'm about to witness a memory corruption. If, instead, I saw "array.wrap(-2)" or "array:wrap[-2]", I would know that something was up and would go find out what was happening. So, in short, I like negative indices, I just prefer to have either: - a special syntax -- "array:wrap[-2]" - a builtin inline routine that looks like a member function of an array "array.wrap(-2)" - a standard inline routine in Phobos that provides the functionality "wrap(array, -2)" Any of these solutions will provide the functionality you want, with much less visual ugliness than seeing a ?: operator at the access point and (by being built in) without having five different names for it from five different authors. It also preserves my ability to write fast code when I need to, without having to resort to "extern (C)" or inline assembly. Mac
Sep 30 2002
parent reply "Walter" <walter digitalmars.com> writes:
"Mac Reiter" <Mac_member pathlink.com> wrote in message
news:an9rsm$1co6$1 digitaldaemon.com...
 One of the problems I have with "ease of programming" over performance is
that
 if I have a language that provides performance, I can make inline
functions to
 provide functionality.  But if my language forces the functionality on me
at the
 expense of performance, I cannot get the performance back without
resorting to a
 lower level language.
Yes, my thoughts exactly.
Oct 08 2002
parent reply Mark Evans <Mark_member pathlink.com> writes:
I answered this remark in an earlier post.  Let's give programmers choices where
possible.  Don't think in terms of a zero-sum game.

Mark
Oct 08 2002
parent "Walter" <walter digitalmars.com> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:anv9gf$2mhv$1 digitaldaemon.com...
 I answered this remark in an earlier post.  Let's give programmers choices
where
 possible.  Don't think in terms of a zero-sum game.
I agree.
Oct 08 2002
prev sibling parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
I believe that forcing *all* array indexing to be slower just so certain
routines can be written a little more easily is not the way to go.

Make a different accessor for negative/positive indexing than normal
positive indexing.

If you blatantly disregard performance issues up front you will likely find
yourself up against a brick wall later trying to optimize algorithms to make
up for a general overall slowness, akin to what you get using VB or Java or
some interpreted language.  At some point they Just Can't Be Made To Run ANY
Faster.

We don't want to put a speed limit on D.  It should be competitive
performance-wise with C/C++ or it won't be used where they are used.  As a
systems programming language, slow array accesses are entirely unacceptable.

As someone who deals with performance issues every day, performance issues
don't always take a back seat.  In realtime apps (games etc) performance
issues are often crucial.  You can't ignore them, and you can't say "well
we'll go back and optimize it later" because your product will get canned if
the publisher doesn't see good progress toward 60 fps.  In fact they often
want it running fast well before it's time to ship.

Sure you shouldn't prematurely optimize, but you also shouldn't go slowing
down the entire language on a whim either.  Not all apps need negative
indexing, but all apps would suffer the performance loss if it were made the
default.

Sean

"Mark Evans" <Mark_member pathlink.com> wrote in message
news:an8chi$2qp4$1 digitaldaemon.com...
 Chris,

 This whole area of array manipulation is one of the huge, gaping holes in
C/C++
 that any replacement language should strive to fix.  I categorically
disagree
 that array (and by extension, string) manipulation is some kind of obscure
 backwater.

 If you focus attention on numerical routines like convolution then you can
 probably isolate cases where negative indices cause a real performance
hit. So
 what.  My experience teaches that coding correctly and quickly is vastly
more
 important.  Performance issues always take a back seat.  I say to you
about
 extreme performance just what you say to me about negative indexing: it's
only
 helpful to a small minority who should be hand-coding anyway.

 I've written literally dozens of convolution routines (1D and 2D) using C
and
 also using script languages.  The first thing I did was to construct a
"negative
 index" system to facilitate the convolution algorithms.  In some languages
that
 was not necessary because it was already built-in.  Guess which languages
I
 preferred?  I would have been in heaven if my C compiler had supported
negative
 indices.

 I've also used negative indexing extensively in Icon string processing and
it
 is a real blessing.  (Consider right-to-left languages, among other
things.) I
 swear, one of these days I am going to port Icon to C, just so I can have
its
 string processing power in C.

 I am beginning to wonder how D will become "a better C++" if nobody wants
 non-C++ features in the language!

 Mark
Sep 30 2002
prev sibling parent reply "Roberto Mariottini" <rmariottini lycosmail.com> writes:
"vb" <none nil.com> ha scritto nel messaggio
news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
In C/C++ you can do it easily: char str[] = "Hello"; char * str_end = str + strlen(str); i str_end[i] 0 \0 -1 o -2 l -3 l -4 e -5 H Is this still possible in D? Ciao
Sep 30 2002
parent "Sandor Hojtsy" <hojtsy index.hu> writes:
"Roberto Mariottini" <rmariottini lycosmail.com> wrote in message
news:an96cn$lci$1 digitaldaemon.com...
 "vb" <none nil.com> ha scritto nel messaggio
 news:Xns9297BBCA6B999whatisthis 63.105.9.61...
 As in python:

 str="Hello"

 [i]     :  -5 -4 -3 -2 -1 0 1 2 3 4
 str[i]  :   H  E  L  L  0 H E L L O

 of course not only for strings, for all arrays.
In C/C++ you can do it easily: char str[] = "Hello"; char * str_end = str + strlen(str); i str_end[i] 0 \0 -1 o -2 l -3 l -4 e -5 H Is this still possible in D? Ciao
Pointers are discouraged. IMHO, a similar D-ish solution would be *reverse slices*.
Sep 30 2002