**FIRST EMAIL**/Java and Orbit Balls *****JAVA DISCUSSION***

[Chris27]

Originally Posted by The Lucas

[SIDE RANT] I think you are missing the point (sorry for the pun). The point of pointer arithmetic is to compute the address of an element (the array data structure is optional). If you can get that address by simply adding to a pointer (stored in a register) that is more efficient than computing that address by loading a symbol and adding the result of a multiplication (indexing an array using a variable).[/SIDE RANT]

And as I stated in my earlier post, both cases boil down to a simple lea instruction in assembly

See, here is a small piece of code I just wrote.

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr = array + i;
11 
12   return 0;
13 }

and its assembly

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 20          	sub    $0x20,%rsp
   8:	bf 28 00 00 00       	mov    $0x28,%edi
   d:	e8 00 00 00 00       	callq  12 <main+0x12>
  12:	48 89 45 f8          	mov    %rax,0xfffffffffffffff8(%rbp)
  16:	c7 45 ec 00 00 00 00 	movl   $0x0,0xffffffffffffffec(%rbp)
  1d:	83 7d ec 09          	cmpl   $0x9,0xffffffffffffffec(%rbp)
  21:	7f 19                	jg     3c <main+0x3c>
  23:	8b 45 ec             	mov    0xffffffffffffffec(%rbp),%eax
  26:	48 98                	cltq   
  28:	48 c1 e0 02          	shl    $0x2,%rax
  2c:	48 03 45 f8          	add    0xfffffffffffffff8(%rbp),%rax
  30:	48 89 45 f0          	mov    %rax,0xfffffffffffffff0(%rbp)
  34:	48 8d 45 ec          	lea    0xffffffffffffffec(%rbp),%rax
  38:	ff 00                	incl   (%rax)
  3a:	eb e1                	jmp    1d <main+0x1d>
  3c:	b8 00 00 00 00       	mov    $0x0,%eax
  41:	c9                   	leaveq 
  42:	c3                   	retq

Alternate code

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr = &array[i];
11 
12   return 0;
13 }

its assembly

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 20          	sub    $0x20,%rsp
   8:	bf 28 00 00 00       	mov    $0x28,%edi
   d:	e8 00 00 00 00       	callq  12 <main+0x12>
  12:	48 89 45 f8          	mov    %rax,0xfffffffffffffff8(%rbp)
  16:	c7 45 ec 00 00 00 00 	movl   $0x0,0xffffffffffffffec(%rbp)
  1d:	83 7d ec 09          	cmpl   $0x9,0xffffffffffffffec(%rbp)
  21:	7f 19                	jg     3c <main+0x3c>
  23:	8b 45 ec             	mov    0xffffffffffffffec(%rbp),%eax
  26:	48 98                	cltq   
  28:	48 c1 e0 02          	shl    $0x2,%rax
  2c:	48 03 45 f8          	add    0xfffffffffffffff8(%rbp),%rax
  30:	48 89 45 f0          	mov    %rax,0xfffffffffffffff0(%rbp)
  34:	48 8d 45 ec          	lea    0xffffffffffffffec(%rbp),%rax
  38:	ff 00                	incl   (%rax)
  3a:	eb e1                	jmp    1d <main+0x1d>
  3c:	b8 00 00 00 00       	mov    $0x0,%eax
  41:	c9                   	leaveq 
  42:	c3                   	retq

Absolutely no difference whatsoever.

[The Lucas]

Originally Posted by Alan Anderson

The efficiency is not what you suggest it is. Pointer arithmetic adds the result of a multiplication too: addition and subtraction are scaled by the size of the structure pointed to.

Originally Posted by AustinSchuh

But, at least in C, the size of the structure is a known quantity at compile time, so I would imagine that most of the time that multiplication can be eliminated by the compiler. And then on top of that, sometimes the multiplication will be by a power of 2, so the compiler will use a cheap shift operation.

Originally Posted by Chris27

And as I stated in my earlier post, both cases boil down to a simple lea instruction in assembly

See, here is a small piece of code I just wrote.

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr = array + i;
11 
12   return 0;
13 }

and its assembly

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 20          	sub    $0x20,%rsp
   8:	bf 28 00 00 00       	mov    $0x28,%edi
   d:	e8 00 00 00 00       	callq  12 <main+0x12>
  12:	48 89 45 f8          	mov    %rax,0xfffffffffffffff8(%rbp)
  16:	c7 45 ec 00 00 00 00 	movl   $0x0,0xffffffffffffffec(%rbp)
  1d:	83 7d ec 09          	cmpl   $0x9,0xffffffffffffffec(%rbp)
  21:	7f 19                	jg     3c <main+0x3c>
  23:	8b 45 ec             	mov    0xffffffffffffffec(%rbp),%eax
  26:	48 98                	cltq   
  28:	48 c1 e0 02          	shl    $0x2,%rax
  2c:	48 03 45 f8          	add    0xfffffffffffffff8(%rbp),%rax
  30:	48 89 45 f0          	mov    %rax,0xfffffffffffffff0(%rbp)
  34:	48 8d 45 ec          	lea    0xffffffffffffffec(%rbp),%rax
  38:	ff 00                	incl   (%rax)
  3a:	eb e1                	jmp    1d <main+0x1d>
  3c:	b8 00 00 00 00       	mov    $0x0,%eax
  41:	c9                   	leaveq 
  42:	c3                   	retq

Alternate code

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr = &array[i];
11 
12   return 0;
13 }

its assembly

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 20          	sub    $0x20,%rsp
   8:	bf 28 00 00 00       	mov    $0x28,%edi
   d:	e8 00 00 00 00       	callq  12 <main+0x12>
  12:	48 89 45 f8          	mov    %rax,0xfffffffffffffff8(%rbp)
  16:	c7 45 ec 00 00 00 00 	movl   $0x0,0xffffffffffffffec(%rbp)
  1d:	83 7d ec 09          	cmpl   $0x9,0xffffffffffffffec(%rbp)
  21:	7f 19                	jg     3c <main+0x3c>
  23:	8b 45 ec             	mov    0xffffffffffffffec(%rbp),%eax
  26:	48 98                	cltq   
  28:	48 c1 e0 02          	shl    $0x2,%rax
  2c:	48 03 45 f8          	add    0xfffffffffffffff8(%rbp),%rax
  30:	48 89 45 f0          	mov    %rax,0xfffffffffffffff0(%rbp)
  34:	48 8d 45 ec          	lea    0xffffffffffffffec(%rbp),%rax
  38:	ff 00                	incl   (%rax)
  3a:	eb e1                	jmp    1d <main+0x1d>
  3c:	b8 00 00 00 00       	mov    $0x0,%eax
  41:	c9                   	leaveq 
  42:	c3                   	retq

Absolutely no difference whatsoever.

Since I'm done my work for the day, I'll continue this rant. What I (and I think Austin too) am getting at is this example (in same style as Chris' examples):

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr = array;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr++;
11 
12   return 0;
13 }

That is different and removes the need for the shift left op (since as Austin said the sizeof(int) is known at compile time and can just be added). Cant do that without explicit pointers. If the multiplication by type size is bothersome you can use an unsigned int and typecast it to a pointer. Also useful if you have an array of structs and are only working with same element in each struct (you can just add the size of the struct to the pointer).

Plus explicit pointers make functions like swap (commonly used in bubblesort simple) simpler using C pass by reference. Again not vital, just something that gets abstracted away in a higher level language.

[Alan Anderson]

Originally Posted by The Lucas

Since I'm done my work for the day, I'll continue this rant. What I (and I think Austin too) am getting at is this example (in same style as Chris' examples):

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr = array;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr++;
11 
12   return 0;
13 }

That is different and removes the need for the shift left op (since as Austin said the sizeof(int) is known at compile time and can just be added). Cant do that without explicit pointers. If the multiplication by type size is bothersome you can use an unsigned int and typecast it to a pointer. Also useful if you have an array of structs and are only working with same element in each struct (you can just add the size of the struct to the pointer).

I don't understand the point (!) of your example. What part of it should I focus on? None of it appears to show me a reason for preferring to use explicit pointers.

Plus explicit pointers make functions like swap (commonly used in bubblesort simple) simpler using C pass by reference...

Isn't pass by reference exactly what Java lets you do in such cases? I guess I'm completely failing to understand what you're trying to explain here.

[The Lucas]

Originally Posted by Alan Anderson

I don't understand the point (!) of your example. What part of it should I focus on? None of it appears to show me a reason for preferring to use explicit pointers.

I generated assembly for both of the examples with the relevant instructions bolded

Originally Posted by Chris27

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr = array + i;
11 
12   return 0;
13 }

.L2:
        cmpl    $9, -12(%ebp)
        jg      .L3
        movl    -12(%ebp), %eax
        sall    $2, %eax
        addl    -4(%ebp), %eax
        movl    %eax, -8(%ebp)
        leal    -12(%ebp), %eax
        incl    (%eax)
        jmp     .L2
.L3:

Originally Posted by The Lucas

 1 #include <stdlib.h>
 2 
 3 int main()
 4 {
 5   int *array = malloc(10 * sizeof(int));
 6   int *ptr = array;
 7   int i;
 8 
 9   for(i = 0; i < 10; i++)
10     ptr++;
11 
12   return 0;
13 }

.L2:
        cmpl    $9, -12(%ebp)
        jg      .L3
        leal    -8(%ebp), %eax
        addl    $4, (%eax)
        leal    -12(%ebp), %eax
        incl    (%eax)
        jmp     .L2
.L3:

So 4 instructions are necessary for ptr = array + i; and only 2 instructions for ptr++; in this assembly language.

Originally Posted by Alan Anderson

Isn't pass by reference exactly what Java lets you do in such cases? I guess I'm completely failing to understand what you're trying to explain here.

I Googled "java swap" and this site explains it pretty well. Basically when you pass by reference to a function in Java it gives the function a new (different) reference to the object and there is no way to change the original reference in the passing function. In C++, the pointer is like an absolute reference (memory location) that is the same everywhere and you can even use pointers to pointers (no references to references in Java).

[Chris27]

Originally Posted by The Lucas;860118
So 4 instructions are necessary for [B

ptr = array + i;[/b] and only 2 instructions for ptr++; in this assembly language.

So what's your point? Of course an expression that contains multiple variables will generally be more complex then an expression that contains a single variable. ptr = (&(ptr[0])) + 1 will again compile to the same assembly. Array indexing is just an encapsulation for pointer arithmetic as I explained earlier. Any pointer arithmetic expression will have a matching array index expression and both of these expressions will compile to the exact same instructions.

I Googled "java swap" and this site explains it pretty well. Basically when you pass by reference to a function in Java it gives the function a new (different) reference to the object and there is no way to change the original reference in the passing function. In C++, the pointer is like an absolute reference (memory location) that is the same everywhere and you can even use pointers to pointers (no references to references in Java).

If you want to change a reference to an object, just have the method return a new reference. If you want a series of references, just encapsulate the references in objects. If you absolutely need to have access to the virtual address of an object, then Java just isn't the right language for the job.

Here is swap with references:

public class MyInt {
	
	int data;
	public MyInt(int x)
	{
		this.data = x;
	}
	
	public static void swap(MyInt a, MyInt b)
	{
		a.data ^= b.data;
		b.data ^= a.data;
		a.data ^= b.data;
	}

}

[The Lucas]

Originally Posted by Chris27

ptr = (&(ptr[0])) + 1 will again compile to the same assembly.

You can't dereference (&) and do pointer arithmetic like that in Java.

Originally Posted by Chris27

Array indexing is just an encapsulation for pointer arithmetic as I explained earlier. Any pointer arithmetic expression will have a matching array index expression and both of these expressions will compile to the exact same instructions.

There is no matching array index expression for this:

ptr = 365;

Array indexing requires a symbol (base of array) and a type (size of element). When an integer can be cast to a pointer, pointer arithmetic can be done without an array.

Originally Posted by Chris27

If you want to change a reference to an object, just have the method return a new reference. If you want a series of references, just encapsulate the references in objects. If you absolutely need to have access to the virtual address of an object, then Java just isn't the right language for the job.

Here is swap with references:

public class MyInt {
	
	int data;
	public MyInt(int x)
	{
		this.data = x;
	}
	
	public static void swap(MyInt a, MyInt b)
	{
		a.data ^= b.data;
		b.data ^= a.data;
		a.data ^= b.data;
	}

}

I know you can create a new class, a similar example was on the page I linked. I just said it was simpler in C. Creating new classes or returning multiple references doesn't sound simple to me.

Again, I understand both languages and the reasons why Java doesn't allow explicit pointers (source of bugs, reference counting for garbage collecting, sercurity, etc..).

Lets revisit how this whole conversion happened (with me paraphrasing)
Billy: Yuck Java. Pointers ftw
Jared: What cant you do with Java references?
Me: Pointer Arithmetic.
Jared: Granted, but you better have a good reason.
<Long posts involving example code by Chris, me and Alan>
I thought twice before pressing Submit Reply on my first post because I knew it wouldn't be my last on this thread Programming debates are interesting (for me atleast) but time consuming. Maybe I should have just let Billy reply or learned from C++ vs LV threads.

[Alan Anderson]

Originally Posted by The Lucas

You can't dereference (&) and do pointer arithmetic like that in Java.

Right. The whole discussion here is based on the lack of pointer arithmetic in Java. But I'm still trying to find out why some think that pointer arithmetic is more efficient than using arrays. My understanding is that they compile to exactly the same thing, since in C a[i] is just syntactical sugar for *(a+i). I used to confuse people by writing i[a] instead, which gives exactly the same result.

There is no matching array index expression for this:

ptr = 365;

Without significant context, I'm at a loss to understand why you'd want to write it. With the exception of using memory-mapped I/O, I have yet to see any examples anywhere where using absolute pointers gives any improvement in efficiency over using arrays.

[Bharat Nain]

Originally Posted by Alan Anderson

Right. The whole discussion here is based on the lack of pointer arithmetic in Java. But I'm still trying to find out why some think that pointer arithmetic is more efficient than using arrays.

More importantly, how much does it matter in our application? What difference will it make?

[Jared Russell]

Originally Posted by Bharat Nain

More importantly, how much does it matter in our application? What difference will it make?

Because if you don't use pointer arithmetic, you can't be a real programmer.

(I know that's not Brian's argument, but it is a good excuse to post one of my all time favorite programming urban legends)

[Greg Needel]

I split this conversation into 2 threads into a java discussion and an orbit ball one.

[EricVanWyk]

Originally Posted by Bharat Nain

More importantly, how much does it matter in our application? What difference will it make?

Bharat just won this thread.

An instruction cycle here or there makes zero difference in the face of the larger picture. If you want to have a truly useless argument, just remember that our new processor is pipelined AND has a double dispatch with multiple ALU elements.

So while you are all optimizing the instructions, I'll be working on what I want the code to do.


As a point of interest, I know someone who wrote his own graphical programming language that compiles to something that is on average twice as fast as C for embedded power and motion control applications.

[Foster]

An instruction cycle here or there makes zero difference in the face of the larger picture. If you want to have a truly useless argument, just remember that our new processor is pipelined AND has a double dispatch with multiple ALU elements.

Right. We now have CPU cycles and memory space to burn, so a cycle here and a cycle there does not make that much difference.

So while you are all optimizing the instructions, I'll be working on what I want the code to do.

I get calls on a regular basis to "make it run faster." I always ask "Does it run correctly now?" since there is no reason to optimize a program that does not work.

As a point of interest, I know someone who wrote his own graphical programming language that compiles to something that is on average twice as fast as C for embedded power and motion control applications.

There are two optimizations here. The custom language is focused to help solve motion control applications. C is a general purpose language, an electronic "hammer" so to speak.

The second is that there is most likely a set of libraries that he uses for the down and dirty interfaces. He optimized them to work with his target platform.

Speed in Java the last few years has come from:

• Improved VM processing - the actual runtime environment of the system
• Improved "code generation" by the compiler
• Improved library functions. By far the biggest speed pickups has been in the optimization of data structures in the system. Sorted lists are about 150% faster due to algorithm improvements (no longer the bumble sort) which then reflects back into the application.

You saw the same things with C and the IFI controller. You could roll your own code to do all the functions, but most of us took Kevin Watson's or the WPI library. Those key functions had been optimized first for "they work" then for "make them fast."

If you optimize the algorithm you seldom have to bit fiddle to make it faster.

[The Lucas]

Originally Posted by Greg Needel

I split this conversation into 2 threads into a java discussion and an orbit ball one.

Sorry for the extra work Greg but it was bound to happen.

Originally Posted by Alan Anderson

Right. The whole discussion here is based on the lack of pointer arithmetic in Java. But I'm still trying to find out why some think that pointer arithmetic is more efficient than using arrays.

It is clear I haven't been a targeting my statements well.

Alan, to show that pointer arithmetic can be more efficient than array indexing, I used ptr++ (cant use in Java) instead of array indexing in Chris' example loop. The generated assembly showed:

Originally Posted by The Lucas

So 4 instructions are necessary for ptr = array + i; and only 2 instructions for ptr++; in this assembly language.

Basically when stepping though an array, you can avoid a multiply(or shift left) op that is need to multiply the index variable by the sizeof that type by simply adding the sizeof to a pointer each time. Incrementing a pointer in a loop is the only pointer arithmetic that I regularly use and the ptr can be even be used as the loop control variable eliminating i.

So basically I am saying (since my first post here) is pointer arithmetic (that can be done in C not Java) can be slightly more efficient in some situations. Nothing major that will make a significant difference in our robot code. Can we agree on that?

Originally Posted by Alan Anderson

My understanding is that they compile to exactly the same thing, since in C a[i] is just syntactical sugar for *(a+i). I used to confuse people by writing i[a] instead, which gives exactly the same result.

Exactly all array indexing is pointer arithmetic. However, not all pointer arithmetic is array indexing. More on that next

Originally Posted by Alan Anderson

Without significant context, I'm at a loss to understand why you'd want to write it. With the exception of using memory-mapped I/O, I have yet to see any examples anywhere where using absolute pointers gives any improvement in efficiency over using arrays.

I accidentally stuck my explanation in the next Chris quote, I fixed it, this is how it should have read

Originally Posted by The Lucas

ptr = 365;

Array indexing requires a symbol (base of array) and a type (size of element). When an integer can be cast to a pointer, pointer arithmetic can be done without an array.

As you said, memory map I/O is the only use I can think of for that expression. However, that wasn't even meant to be a practical example. It was just meant provide an simple example of pointer arithmetic that didn't have a matching array index expression to refute Chris' statement:

Originally Posted by Chris27

Array indexing is just an encapsulation for pointer arithmetic as I explained earlier. Any pointer arithmetic expression will have a matching array index expression and both of these expressions will compile to the exact same instructions.

Originally Posted by Jared341

Because if you don't use pointer arithmetic, you can't be a real programmer.

(I know that's not Brian's argument, but it is a good excuse to post one of my all time favorite programming urban legends)

Great story