Closed Bug 408368 Opened 12 years ago Closed 12 years ago

Suboptimal code in array_sort implementation

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla1.9beta3

People

(Reporter: igor, Assigned: ehsan)

References

()

Details

Attachments

(1 obsolete file)

[This is a spin-off of bug 403977 comment 86]

Since the patch for bug 403977 landed array_sort from jsarray.c has being containg the following code:


    if (newlen == 0)
        goto out;
....
            for (i = 0; i < newlen; ++i) 
                vec[i] = vec[2 * i + 1];
...
out:

Although it is known that in the loop above newlen is non-zero and the loop will run at least once, the code uses a for-loop for clarity. The assumtion is that a compiler can optimize it into the corresponding do-loop:

i = 0;
do {
   vec[i] = vec[2 * i + 1];
} while (++i == newlen);

Unfortunately the reality is not that bright. For example, with GCC 4.1.2 such transformation does not happen at -Os optimization level. Here is an assembler code for the for-loop: 

	xorl	%edx, %edx
	cmpl	$0, -76(%ebp)
	je	.L651
	jmp	.L649
.L652:
	movl	-96(%ebp), %ecx
	movl	4(%ecx,%edx,8), %eax
	movl	%eax, (%ecx,%edx,4)
	incl	%edx
.L651:
	cmpl	-88(%ebp), %edx
	jne	.L652
	jmp	.L649

Changin the source into the corresponding do-while loop leads to:  

	xorl	%edx, %edx
.L651:
	movl	-96(%ebp), %ecx
	movl	4(%ecx,%edx,8), %eax
	movl	%eax, (%ecx,%edx,4)
	incl	%edx
	cmpl	-88(%ebp), %edx
	je	.L649
	jmp	.L651
.L634:

That is, with the for-loop GCC generates extra instructions to check for zero i:

	cmpl	$0, -76(%ebp)
	je	.L651
	jmp	.L649

Thus I suggest to change the for-loop to the explicit do-while implemnentation.
Depends on: 403977
Assignee: general → ehsan.akhgari
Target Milestone: --- → mozilla1.9 M11
Attached patch Patch (v1) (obsolete) — Splinter Review
Simple patch implementing the suggested change in comment 0.
Attachment #293146 - Flags: review?(crowder)
Status: NEW → ASSIGNED
(In reply to comment #0)
> Although it is known that in the loop above newlen is non-zero and the loop
> will run at least once, the code uses a for-loop for clarity. The assumtion is
> that a compiler can optimize it into the corresponding do-loop:
> [...]

I never assumed that.  I think being able to read the code at a glance is much more important than saving three instructions in the third-most-likely branch of a routine that does O(N log N) string compares.  Clear code has fewer bugs and is easier to work with.
Comment on attachment 293146 [details] [diff] [review]
Patch (v1)

No patch needed here, I've simply reverted the code in the original bug back to the code Igor originally wrote, and for which we have r+/a+
Attachment #293146 - Flags: review?(crowder) → review-
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
(In reply to comment #2)
I think being able to read the code at a glance is much
> more important than saving three instructions...

As regarding the clarity, the whole code looks like:

do {
   expand loop
} while ();
...
MergeSort
...
do {
  shrink loop
} while ();

where the first case can not be replaced with easy to read for-loop. So to understand what is going on one has to grasp the first do-loop. 

For me it is simpler to follow and check for correctness the second loop if it follows the same do-while pattern. And it fact it was easier to write it this way: I cut&pasted the first loop and than changed the initialization and the while conditions.
Flags: in-testsuite-
Flags: in-litmus-
Comment on attachment 293146 [details] [diff] [review]
Patch (v1)

>+            i = 0;
>+            do {
>                 vec[i] = vec[2 * i + 1];
>+            } while (++i == newlen);

This patch would've introduced a bug.
(In reply to comment #5)
> (From update of attachment 293146 [details] [diff] [review])
> >+            i = 0;
> >+            do {
> >                 vec[i] = vec[2 * i + 1];
> >+            } while (++i == newlen);
> 
> This patch would've introduced a bug.
> 

What bug?
(In reply to comment #6)
> (In reply to comment #5)
> > (From update of attachment 293146 [details] [diff] [review] [details])
> > >+            i = 0;
> > >+            do {
> > >                 vec[i] = vec[2 * i + 1];
> > >+            } while (++i == newlen);
> > 
> > This patch would've introduced a bug.
> > 
> 
> What bug?
> 

Should have been:

+            i = 0;
+            do {
                 vec[i] = vec[2 * i + 1];
+            } while (++i <= newlen);
Attachment #293146 - Attachment is obsolete: true
Igor's original version has it as while (++i != newlen), which is fine.
You need to log in before you can comment on or make changes to this bug.