www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - NDim-slicing

reply Norbert Nemec <Norbert_member pathlink.com> writes:
Hi there,

after two years of silence, I just found a little time to return my thoughts to
D and the issues of NDim-arrays I started back then. (No, I never completely
forgot about D, I just had other things that I had to give priority.)

My design proposal for NDim arrays needs a complete overhaul before discussion
of details makes sense. However, there is one cucial issue that needs to be
solved and I have no idea how it could be done:

Currently we have OpIndex and OpIndexAssign fit for overloading multidimensional
indexing. OpSlice and OpSliceAssign, however, work only for one dimension. I've
been thinking how to generalize these, but it turns out to be extremely tricky.
First though is: Why not simply extend OpSlice to take N pairs of boundaries?
But then, what about mixed expressions like 'a[1,4..7]' ?

Working with Python, I use expressions like that all the time, and I think it is
crucial that Ndim-arrays in D allow this kind of slicing as well. For native
Ndim arrays, it should be straightforward to handle such expressions in the
compiler. However, how should they be overloaded?!?

Python goes the way of taking a tuple of objects as indices where '4..7' would
then be translated into a "slice object". The indexing-overloading routine then
goes through all the objects at run-time and decides whether each one is a
slicing or an indexing operation. All of this is rather simple with dynamic
typing and accepting the run-time overhead.

In D, this is not an option. Indexing/Slicing has to be type-safe and the
resulting type has to be known at compile time.

One rather clumsy solution that I came up so far is to split the resolve the
expression into two consecutive function calls:
a[1,4..7]
would become
a.OpIndexPartial(0,1).OpSlice(4,7)
where the first function is defined as
OpIndexPartial(int dim,int idx)
and returns an array one rank lower.

The assignment expression:
a[1,4..7] = b[0..3]
would turn into
a.OpIndexPartial(0,1).OpSliceAssign(b[0..3],4,7)

The ugly thing about this solution is, that some kind of marshal-object is
needed which is returned from OpIndexAssign.


Another possibility would be to change
OpSlice(size_t start, size_t end)
into
OpIndex(size_t[2] slc)
and interpret a complex expression like
a[1,3..5,2,6..3]
as a call to
OpIndex(size_t idx0, size_t[2] slc1, size_t idx2, size_t[2] slc3)
I don't know, however, whether D templates would allow to implement the long
list of routines in some comfortable way.

All the really clean solution that I could think of would demand for tuple-types
and list-handling at compile time, both things that have been discussed before
but are at best a topic for the very far future.

Any ideas?
Mar 10 2006
parent reply pragma <pragma_member pathlink.com> writes:
Perhaps I'm missing the boat, or maybe its just that long since you posted the
original NDim array proposal, but what were the advantages to adding NDim arrays
in D?

The reason why I ask is that aside from using rectangular arrays for the
purposes of reducing computational and storage overhead, for very specific tasks
(bitmap manipulation and matrices come to mind), the current soluiton in D works
quite well.  After all, it doesn't get any more simple, reliable and easy to
implement than limiting every array to exactly one dimension.  It's also quite
elegant in that by disallowing rectangular arrays, the problems with wielding
all of the variations in slicing and indexing become far less bothersome: this
last fact is unintentionally implied by your most recent post.

I'm genuinely curious since you've obviously put a lot of effort behind all
this, and I'm very much in the dark as to why.  Could you please enlighten me?
:)

Thanks,


- EricAnderton at yahoo
Mar 10 2006
parent reply pragma <pragma_member pathlink.com> writes:
Open mouth, insert foot.

Norbert, all, 
Please disregard my last post and critique regarding rectangular arrays.  It
seems that I need to read the docs a little more carefully next time as D does
indeed support them. :(

- EricAnderton at yahoo
Mar 10 2006
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
pragma wrote:
 Open mouth, insert foot.
 
 Norbert, all, 
 Please disregard my last post and critique regarding rectangular arrays.  It
 seems that I need to read the docs a little more carefully next time as D does
 indeed support them. :(
I think you should take that foot out of your mouth again. The questions in the last message were not that pointless after all: Indeed the documentation talks about something called "rectangular arrays". However this concept only exists for static arrays, i.e. for arrays, where the size of all dimensions is known at compile time. What is seriously missing are dynamic rectangular arrays. Your first question, why these are seriously missing can be answered in several ways * reducing computational and storage overhead using "dynamical arrays of dynamical arrays" means that every access to the data takes two dereferencing operations. Furthermore all the rows of the arrays have to be allocated separately, contributing to memory fragmentation. * greatly enhancing the comfort of handling NDim data especially in the field of numerical computation -- which is a core part not only of scientific computing, but also also of game programming, image processing and many other fields of programming -- handling NDim-data is the daily bread of the programmer. It may not be an issue to every programmer, but there certainly is a huge group of potential D users who will consider NDim-array handling a crucial language feature. * preparing the path towards vectorized expressions this goes beyond "reducing overhead" towards "enabling tremendous optimization potential". The first two points might be solvable by an array library, but I believe that NDim arrays are such a core feature that they deserve native support. When we last discussed this issue two years ago, most people -- including Walter -- agreed that this should eventually become part of the language, even though it did not get highest priority. The "Future plans" page of the D homepage contains the point "Array literal expressions" (which is, what I generalized under the term "vectorized expressions") -- I believe that the issue of multidimensional arrays should be solved first, before touching the issue of array expressions. Both depend strongly no each other. Doing one step without thinking of the others will make it a lot more difficult in the end.
 
 - EricAnderton at yahoo
pragma wrote:
 Perhaps I'm missing the boat, or maybe its just that long since you
posted the
 original NDim array proposal, but what were the advantages to adding
NDim arrays
 in D?

 The reason why I ask is that aside from using rectangular arrays for the
 purposes of reducing computational and storage overhead, for very
specific tasks
 (bitmap manipulation and matrices come to mind), the current soluiton
in D works
 quite well.  After all, it doesn't get any more simple, reliable and
easy to
 implement than limiting every array to exactly one dimension.  It's
also quite
 elegant in that by disallowing rectangular arrays, the problems with
wielding
 all of the variations in slicing and indexing become far less
bothersome: this
 last fact is unintentionally implied by your most recent post.

 I'm genuinely curious since you've obviously put a lot of effort
behind all
 this, and I'm very much in the dark as to why.  Could you please
enlighten me?
 :)

 Thanks,


 - EricAnderton at yahoo
Mar 11 2006
parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Norbert Nemec wrote:
 pragma wrote:
 
Open mouth, insert foot.

Norbert, all, 
Please disregard my last post and critique regarding rectangular arrays.  It
seems that I need to read the docs a little more carefully next time as D does
indeed support them. :(
I think you should take that foot out of your mouth again. The questions in the last message were not that pointless after all: Indeed the documentation talks about something called "rectangular arrays". However this concept only exists for static arrays, i.e. for arrays, where the size of all dimensions is known at compile time. What is seriously missing are dynamic rectangular arrays.
I am badly missing this. A feature too fundamental to be missing (imo).
Mar 12 2006