Closed
Bug 408368
Opened 17 years ago
Closed 17 years ago
Suboptimal code in array_sort implementation
Categories
(Core :: JavaScript Engine, enhancement)
Core
JavaScript Engine
Tracking
()
RESOLVED
FIXED
mozilla1.9beta3
People
(Reporter: igor, Assigned: ehsan.akhgari)
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.
Assignee | ||
Updated•17 years ago
|
Assignee: general → ehsan.akhgari
Target Milestone: --- → mozilla1.9 M11
Assignee | ||
Comment 1•17 years ago
|
||
Simple patch implementing the suggested change in comment 0.
Attachment #293146 -
Flags: review?(crowder)
Assignee | ||
Updated•17 years ago
|
Status: NEW → ASSIGNED
Comment 2•17 years ago
|
||
(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 3•17 years ago
|
||
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-
Updated•17 years ago
|
Status: ASSIGNED → RESOLVED
Closed: 17 years ago
Resolution: --- → FIXED
Reporter | ||
Comment 4•17 years ago
|
||
(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.
Updated•17 years ago
|
Flags: in-testsuite-
Flags: in-litmus-
Comment 5•17 years ago
|
||
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.
Comment 6•17 years ago
|
||
(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?
Assignee | ||
Comment 7•17 years ago
|
||
(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);
Assignee | ||
Updated•17 years ago
|
Attachment #293146 -
Attachment is obsolete: true
Comment 8•17 years ago
|
||
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.
Description
•