4 ms·
I hadn't thought of writing a tail-recursive dumbsort, though I'm not sure this is really simpler (untested): void dumbsort(int *p, size_t n) {
by kragen 5y ago
I hadn't thought of writing a tail-recursive dumbsort, though I'm not sure this is really simpler (untested):
void
dumbsort(int *p, size_t n)
{
dumbsort2(p, n, 1);
}
int
dumbsort2(int *p, size_t n, size_t i)
{
int tmp;
return i == n ? 0
: p[i] < p[i-1] ? (tmp = p[i],
p[i] = p[i-1],
p[i-1] = tmp,
dumbsort2(p, n, 1))
: dumbsort2(p, n, i+1);
}
> If the common case can be a single opcode like LOOP
The thing about the 8086 LOOP instruction is that it does expose the loop counter conveniently; it's just CX (or ECX on i386, RCX on amd64). So restarting it is just a MOV (not an XOR, because it counts down to 0).
Forth offers an instructive example of a set of operations (usually implemented in software rather than hardware) that support nested loops. Forth DO pushes both the loop counter and the upper bound on the "return stack" as what the ANSI standard calls a "do-sys"; there are words I, J, and K which get the innermost, second-innermost, and third-innermost loop counters, but cannot be used to set them. You can even save the contents of the return stack and restore it, but ANSI doesn't give you a way to restart the loop counter (which is certainly bad practice).
But that's just a matter of portability; any concrete Forth necessarily has to have a reliable way to set the loop counter so that LOOP can increment it. For CPUs, that circuitry wouldn't have to be accessible as an instruction, but general-purpose CPUs have a different concern: they need to have some way to save and restore all their architectural registers for preemptive context switching, which would include that loop counter — even if it wasn't exposed as a GPR like the i386 ECX. You could imagine providing that ability only via something like i386 PUSHAD, which would be a pretty inconvenient and slow way to restart the loop counter. But I'm not familiar with any instruction sets that work that way.
> Is there a way to write gnomesort that only has two simple conditionals? You're right that my suggestion brings it a lot closer to gnomesort, but I'm definitely not suggesting anything that checks if you're at zero.
I think that if you have a signed max() instruction that doesn't count as a conditional, this produces gnomesort with only two simple conditionals (untested):
void
browniesort(int *p, size_t n)
{
int tmp;
for (size_t i = 1; i < n; i++) {
if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = max(i-2, 0);
}
}
I was thinking that maybe the "standard" gnome sort avoids redundantly comparing the first two entries again after swapping them, instead immediately stepping forward, but in fact both Dick Grune's C at https://dickgrune.com/Programs/gnomesort.html https://dickgrune.com/Programs/gnomesort.html and the pseudocode in https://en.wikipedia.org/wiki/Gnome_sort https://en.wikipedia.org/wiki/Gnome_sort do the same redundant comparison of the two items they just swapped. (Hamid Sarbazi-Azad's original "stupid sort" does not do this, but Grune considers it "the same algorithm".)
I think not counting max() as a conditional may be reasonable because, as I said, a number of CPU instruction sets provide it as a fundamental operation. At the hardware level it's no more conditional than the multiplexers used to read an operand from a source register in the register file.
- Dylan16807 5y ago> I hadn't thought of writing a tail-recursive dumbsort, though I'm not sure this is really simpler (untested): I meant something more like this: void dumbsort(int *p, size_t n) { int tmp; for (size_t i = 1; i < n; i++) { if (p[i] < p[i-1]) { tmp = p[i]; p[i] = p[i-1]; p[i-1] = tmp; return dumbsort(p, n); } } The same as the original except it doesn't need to manipulate the loop variable. In the assembly version, you replace wiping eax with a jump.
- kragen 5y agoOh, of course you're right. In FORTH you'd need an UNLOOP there if you were using a DO LOOP. It's kind of bogus that the 8086 loop-counter register CX isn't one of the index registers, isn't it?