Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Accessing array elements via floating point formats. (http://www.velocityreviews.com/forums/t739928-accessing-array-elements-via-floating-point-formats.html)

Skybuck Flying 12-10-2010 07:56 PM

Accessing array elements via floating point formats.
 
Hello,

Perhaps the intel instruction set has a little bit of a problem.

As far as I know memory cells/access can only be done via integers.

Thus programming languages like C and Pascal/Delphi need to write code as
follows:

ArrayElement[ vIndex ] = ...;

Where vIndex always has to be an integer ?!?

This leads to problems where some code works with floating points and some
with integers.

Since floating points can represent integers as well, floating points could
be considered more "universal" data types.

Therefore it makes more sense to access memory cells via floating points
than integers.

This would allow the programmers to write code once and use the floating
point formats for pretty much everything: calculations and array lookups.

So my suggestion for intel/amd is to add new instructions to the instruction
set so that memory lookups can be done via floating points. (The whole
numbers of the floating points could then be used for lookups, the
fractional part is ignored).

As far as I know C cannot do this currently for x86 compilers ?

I think the following C code will probably not compile:

SomeArray[ vIndex ] = 5;

Where vIndex is some floating point ?

An easy solution would ofcourse be to call something like round or ceil or
floor...

But having to call such routines all the time seems a bit
overheadish/excessive.

Therefore perhaps instructions and hardware can do it much faster so this
problem would be a thing of the past ?!? (And ofcourse the necessary
compiler extensions/features/modifications for easy programming like
above...)

(Ofcourse floating points would have a little drawback because their
range/precision is limited to 24 bit for 32 bit IEEE floating point
format... and also 48 or something for 64 bit floating point format... but
for many purposes this would probably be enough... so the idea of using
floating points for memory lookups remain interesting and usefull ! ;) )


Bye,
Skybuck.



Skybuck Flying 12-10-2010 08:13 PM

Re: Accessing array elements via floating point formats.
 

"The China Blue and the Gray" <chine.bleu@yahoo.com> wrote in message
news:chine.bleu-DDD34B.11595610122010@news.eternal-september.org...
> In article <b0b9d$4d0285f0$54190f09$9110@cache2.tilbu1.nb.hom e.nl>,
> "Skybuck Flying" <IntoTheFuture@hotmail.com> wrote:
>
>> I think the following C code will probably not compile:
>>
>> SomeArray[ vIndex ] = 5;
>>
>> Where vIndex is some floating point ?

>
> It will work. The compiler emits code to truncate a real to an int before
> addressing the array.


You lie.

Visual Studio 2008 compiler returns:

"Error 2 error C2108: subscript is not of integral type y:\c testen\test
array access via floating points\version 0.01\main.cpp\main.cpp.cpp 28
Main.cpp"

You had me going there for a moment ?! ;) :)

Bye,
Skybuck =D



Skybuck Flying 12-10-2010 08:31 PM

Re: Accessing array elements via floating point formats.
 

"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnvd31xrcx.fsf@nuthaus.mib.org...
> The China Blue and the Gray <chine.bleu@yahoo.com> writes:
>> In article <b0b9d$4d0285f0$54190f09$9110@cache2.tilbu1.nb.hom e.nl>,
>> "Skybuck Flying" <IntoTheFuture@hotmail.com> wrote:
>>
>>> I think the following C code will probably not compile:
>>>
>>> SomeArray[ vIndex ] = 5;
>>>
>>> Where vIndex is some floating point ?

>>
>> It will work. The compiler emits code to truncate a real to an int before
>> addressing the array.

>
> Apparently neither one of you bothered to try it (or check the
> C standard) before posting. It's a constraint violation.
> C99 6.5.2.1p1.
>
> Followups redirected to comp.lang.c.


Followups redirected to originals, because this is interesting for other
languages too... especially Delphi ;) =D

http://www.open-std.org/jtc1/sc22/WG...docs/n1256.pdf

"
6.5.2.1 Array subscripting

Constraints

1 One of the expressions shall have type ''pointer to object type'', the
other expression shall
have integer type, and the result has type ''type''.

Semantics

2 A postfix expression followed by an expression in square brackets [] is a
subscripted
designation of an element of an array object. The definition of the
subscript operator []
is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion
rules that
apply to the binary + operator, if E1 is an array object (equivalently, a
pointer to the
initial element of an array object) and E2 is an integer, E1[E2] designates
the E2-th
element of E1 (counting from zero).

3 Successive subscript operators designate an element of a multidimensional
array object.
If E is an n-dimensional array (n >= 2) with dimensions i x j x . . . x k,
then E (used as
other than an lvalue) is converted to a pointer to an (n - 1)-dimensional
array with
dimensions j x . . . x k. If the unary * operator is applied to this pointer
explicitly, or
implicitly as a result of subscripting, the result is the pointed-to (n -
1)-dimensional array,
which itself is converted into a pointer if used as other than an lvalue. It
follows from this
that arrays are stored in row-major order (last subscript varies fastest).

4 EXAMPLE Consider the array object defined by the declaration
int x[3][5];
Here x is a 3 5 array of ints; more precisely, x is an array of three
element objects, each of which is an
array of five ints. In the expression x[i], which is equivalent to
(*((x)+(i))), x is first converted to
a pointer to the initial array of five ints. Then i is adjusted according to
the type of x, which conceptually
entails multiplying i by the size of the object to which the pointer points,
namely an array of five int
objects. The results are added and indirection is applied to yield an array
of five ints. When used in the
expression x[i][j], that array is in turn converted to a pointer to the
first of the ints, so x[i][j]
yields an int.
Forward references: additive operators (6.5.6), address and indirection
operators
(6.5.3.2), array declarators (6.7.5.2
"

Pretty short text for such an important feature as array operator [].

Anyway as far as I can tell this text mentions integers only, so no floating
points. (also forward references do not seem to mention floating points).

This is what I would like to see changed in the future for easier
programming.

Also the intel instruction manual says registers have to be filled with
byte, word or doubleword.

I hope to see that changed as well by "floating point" and "double floating
point".

How they make that work is up to them to come up with some nice solution...
perhaps setting a flag somewhere in the instructions to indicate
"floating point lookups".

Then when it happens it can be stuffed into C compilers and then hopefully
it will soon ripple/trickle down to the Delphi compiler !

So I can finally use it in Delphi too ! ;) =D YEAHAHAHAHAHAHA ! =D

Bye,
Skybuck =D



Skybuck Flying 12-10-2010 08:40 PM

Re: Accessing array elements via floating point formats.
 
I can already imagine a debate about should it be rounded up, or down...

Some algorithms might like it down, and some might like it up.

So perhaps a special array operator could be created to make both possible
as follows:

SomeArray< vIndex ] = 666; // rounds vIndex down.
SomeArray[ vIndex > = 666; // rounds vIndex up.

Could also be something like:

SomeArray[ <vIndex ] = 666;
SomeArray[ vIndex> ] = 666;

or

SomeArray[ <vIndex ] = 666;
SomeArray[ >vIndex ] = 666;

This last one seems kinda nice... not sure if operator > is already being
used in subscripts... probably not ? at least not in delphi or I could be
wrong ;)... perhaps in C it's already used... for comparisions... well
that's C problems... hehe.

Alternatively it could always be simply down... the up algorithms would
simply write:

SomeArray[vIndex+1] = 666;

Yeah... I think that is best. No extra syntax needed... rounding is
consistent...

Towards zero... Negative index -1.4 would go to -1. and -1.5 would also go
to -1

I think that's general floor behaviour but I am not sure...
I don't think floor(-1.5) would be -2 ? it would be -1 ?! since 2 is larger
negative ;) :)

So my recommendation:

Floor it and love it ! =D ;)

Bye,
Skybuck =D



Keith Thompson 12-10-2010 09:14 PM

Re: Accessing array elements via floating point formats.
 
The China Blue and the Gray <chine.bleu@yahoo.com> writes:
> In article <b0b9d$4d0285f0$54190f09$9110@cache2.tilbu1.nb.hom e.nl>,
> "Skybuck Flying" <IntoTheFuture@hotmail.com> wrote:
>
>> I think the following C code will probably not compile:
>>
>> SomeArray[ vIndex ] = 5;
>>
>> Where vIndex is some floating point ?

>
> It will work. The compiler emits code to truncate a real to an int before
> addressing the array.


Apparently neither one of you bothered to try it (or check the
C standard) before posting. It's a constraint violation.
C99 6.5.2.1p1.

Followups redirected to comp.lang.c.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Skybuck Flying 12-10-2010 09:19 PM

Re: Accessing array elements via floating point formats.
 
Hmm basic seemed to allowed floating point indexes since basic only had the
"real" type... according to this book...

I mention this book because it seems quite nice... most of it I probably
already know... some of it maybe not... from the looks of it... I would
highly recommend it to IT schools/colleges, since this book seems to contain
pretty much most of the basics of writing great code.

Therefore I think this book is worthy of a mention by me ! ;) :):

"Write Great Code: Volume 1: Understanding the machine by Randall Hyde"

http://www.amazon.com/Write-Great-Co...der_1593270038

(Link is to paperback form... I would prefer the big book (if I was in
school)... so keep on searching young-jedi's ! ;) :) (Me I will probably rip
an PDF sometime :P* ;) :))

Bye,
Skybuck =D



Skybuck Flying 12-11-2010 12:06 AM

Re: Accessing array elements via floating point formats.
 
<snipped none important stuff>

(why comp.arch only ? are the other groups not available to you ? setting it
back because others might enjoy it as well, and to prevent same
discussions.)

> This leads to problems where some code works with floating points and some
> with integers.


"
What makes you think this is a problem?
"

Currently I want to implement a polygon in software.

Now I have a dillema:

Should it be a polygon with integer coordinates.

or

Should it be a polygon with floating point coordinates.

GDI might like the integer version.

OpenGL might like the floating point version.

Bitmaps/Pixels will surely like the integer version.

> Since floating points can represent integers as well, floating points
> could
> be considered more "universal" data types.


"
So could ASCII text--since you can represent anything in ASCII (or
EBCIDIC or even FIELD DATA). Are you suggesting that any and every
system with greater expressive potential than integers be used to
access elements from arrays?
"

Unicode is all the rage why now... so those things you mentioned are now
pretty much dead.

> Therefore it makes more sense to access memory cells via floating points
> than integers.


"
No, it does not. Floating point numbers can represent fractional
values, and attempting to define what address to read when::
"

I think it does for a number of reasons:

1. Easier and faster to write code.
2. No need for multiple data structures which more or less do the same
thing.
3. Faster hardware support. Support in the instructions would probably be
much
faster than calling a typecast or round or floor all the time ?!

"
array[ 3.141592653 ] is problematic at best--even at the definitional level.
"

I don't think so, but let's see what you came up with ;) :)

"
A) should we extend the notion of fractional memory addresses to be
individual bits?
"

This is an extension of the idea.

The integer part is at least the clear part... it addresses the element, be
it a record or a primitive data type.

For primitive data types the fractional part could indeed address individual
bits.

"
B) should the number be rounded, in what direction, or truncated?
"

See follow up post, floor would be nice since that would be very consistent,
follow the usual/math best practice of starting offsets from 0 and is easy
to convert
to ceil by adding +1 in the code itself.

"
C) what do you do with negative zeros?
"

Treat them the same as positive zeros ?

"
D) does the hidden bit participate in the address calculation?
"

I forgot what the hidden bit is for... it's the 24th bit ?

The goal would be to maximize the addressible range with perfect precision.

So if it's possible to include the 24th bit with that goal in mind then yes.

"
E) what address do you reference with Infinities, NANs, denormals?
"

This would throw an exception. Like a null pointer, access violation,
something
like that.


"
F) what address to you reference if there is massive cancelation in
the address calculation?
"

I am unfamiliar with this. However if the floating point number goes out of
range of the array then
an access violation could occur.

It could also be the responsibility of the compiler to add range checking
code.

It could also be the responsibility of the programmer to know when this
happens and solve
it himself.

Perhaps the processor could also help with this case if it's really a big
problem... by throwing
some sort of error again like an exception. Perhaps a floating point
exception.

"
If you want to see what happens when an architecture attempts to use
floating point numbers as memory references, look into the Bouroughs
6700.
"

Sounds like old stuff... hard to look at old stuff ! ;) :)

What would I be looking for anyway ? Hardware or software ?

Do you have some examples/links ?

"
Another problem is that FP numbers take considerably more time to
process than integers. An integer add takes roughly 1/2 cycle, a FP
add takes roughly 2.5 cycles for a 5X penalty in the critical cache
lookup pipeline.
"

Why is that ? Is it a theoretical slowness or is it just that hardware
currently is faster
for integers ?

Ultimately the question is what would be faster:

Special instructions or current situation with calling floor/round functions
or instructions.

I would expect the special instructions solution would still be faster and
thus worthy to have
a look at, and the added benefit is easier software.

"
The <sane> architects decided long ago to require programmers to
specify memory addresses down to the smallest unit the memory system
supports,"

A bit ? a byte ? ?

"
and no fraction thereof. No <sane> architect (or <sane>
architect wannabe {hint: you}) will ever inflict this kind of penalty
on an architecture that is supposed to survive more than one
generation.
"

I am not a hardware architect... yet I see no reason why an architecture
could not support both methods.

Integer lookups and floating point lookups.

This discussion of what is wise or not wise hardware-wise is up to you
hardware people.

As a software person I would say yes this would be quite nice to have.

"
I think, in general, it is WISE to prevent FP numbers from being used
as addresses because of various memory aliasing problems remaining in
"

Memory aliasing problem ?

You mean a delphi alias ?
var
a : integer;
b : integer alias a; // something like that ?


"
languages and programs--so that attempting to dereference with a
floating point bit pattern will result in a memory fault detected by
the MMU."

So what is the problem ?

If the problem is that current hardware can't do it because they way it was
designed than ofcourse
that hardware will either need to be changed but could break compatibility
or an addition needs to be made
to make it possible after all...

Again that's the hardware designers problem... not my problem as a software
programmer.

Conceptually for software it's not a problem.

"
Secondly, what do you do when the size of addressible virtual
memory becomes larer than the fraction portion of the floating point
number?
"

Again not really a problem, this limitation already exists.

The programmer is limited to 24 bits or 48 bits address range.

The programmer is simply limited, something which he should understand.

This feature is not ment to be able to address any region of the memory.

This feature is ment to address from the base address of the array.

The final computed address could be an integer.

"
Languages such as APL have used FP numbers as the target address for
GOTOs, but this requires the interpreter to <search> a list of
statement tags to find the next sequence of instructions.

Mitch
"

?

Sounds slow, I am definetly not interested in slow stuff or anything I have
to type extra's ! ;) :)

Bye,
Skybuck.



Nobody 12-11-2010 12:12 PM

Re: Accessing array elements via floating point formats.
 
On Sat, 11 Dec 2010 01:06:06 +0100, Skybuck Flying wrote:

> Currently I want to implement a polygon in software.
>
> Now I have a dillema:
>
> Should it be a polygon with integer coordinates.
>
> or
>
> Should it be a polygon with floating point coordinates.
>
> GDI might like the integer version.
>
> OpenGL might like the floating point version.


OpenGL will accept either. Using integers would at least provide
consistency with GDI.

> Bitmaps/Pixels will surely like the integer version.


Integer vertex coordinates don't present any inherent advantage for
rasterisation.

> 3. Faster hardware support. Support in the instructions would probably
> be much faster than calling a typecast or round or floor all the time ?!


You don't "call" a typecast; it's a language feature. And floor()
etc are going to be inlined on any sane platform when optimisations are
enabled. It makes no difference whether the rounding/truncation is
explicit or implicit.

> Another problem is that FP numbers take considerably more time to
> process than integers. An integer add takes roughly 1/2 cycle, a FP add
> takes roughly 2.5 cycles for a 5X penalty in the critical cache lookup
> pipeline.
> "
>
> Why is that ? Is it a theoretical slowness or is it just that hardware
> currently is faster for integers ?


FP addition requires normalising the significands first. This adds an
inevitable latency penalty (you have to finish subtracting the exponents
before you can start adding the significands), and requires either more
gates or more cycles.


George Neuner 12-12-2010 12:37 AM

Re: Accessing array elements via floating point formats.
 
On Sat, 11 Dec 2010 15:09:39 -0800, "Andy \"Krazy\" Glew"
<andy@SPAM.comp-arch.net> wrote:

>By the way, there *ARE* instructions that can be used to access memory
>with addresses originally calculated in floating point.
>
>In C, you can do:
>
> float x = rand();
> int a[66];
> a[1] = a[ (unsigned)(x * 66) ];
>
>But if you note a possible buffer overflow here, well, that's another
>reason against FP addresses.
>
>Anyway... you *can* create addresses in FP: they just get converted to
>int, via compiler added instructions, before the memory reference.
>
>You would be well justified by saying that these instruction sequences
>are clunky, and often really, Really, REALLY slow. However, if they
>were used more often, they would probably be made faster.


These kinds of FP->int sequences are used routinely for indexing into
interpolation tables. And there are a *LOT* of people who would be
happier if it could be done faster.

George

Malcolm McLean 12-12-2010 07:26 AM

Re: Accessing array elements via floating point formats.
 
On Dec 12, 1:09*am, "Andy \"Krazy\" Glew" <a...@SPAM.comp-arch.net>
wrote:
>
> And it goes against history, and *is less modular. *The historical trend
> being the separation of integer and FP I mentioned above; the modularity
> being that this separation allows the integer and address datapaths to
> be completely separate from the FP data paths.
>

Most programming projects that fail do so because the interactions
between the various parts of the program become too complex to manage,
not because the processor isn't fast enough. So pipelineing issues are
secondary.

However integers and real usually mean different things. Reals tend to
be measurements of values. Integers tend to be indicies into a table/
array. Also many variables hold intermediate results during the course
of calculations, of course.




All times are GMT. The time now is 02:54 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.