Algorithm Challenge

[xvedejas]

Code: Select all

uint32_t pool_alloc(pool_t *pool) {
   inline void full() {
      printk("%x\n", pool_query(pool));
      panic("pool allocator full");
      return 0;
   }
   uint32_t p, w, b;   // pool, word, bit

   // Find suitable pool
   for (p = 0; pool[p].total == 0; p++)
      if (pool[p].setup != 0x4224) full();
   if (pool[p].setup != 0x4224) full();

   // Find suitable word within pool
   for (w = pool[p].first / 32; w < pool[p].upper / 32; w++)
      if (pool[p].word[w] != 0xFFFFFFFF) break;

   // Find open bit within word
   for (b = 0; pool[p].word[w] & (0x1 << b); b++);
   if (b == 32) full();

   pool[p].word[w] |= (0x1 << b);
   pool[p].total --;
   if (pool[p].first == ((w << 5) | b)) pool[p].first++;
   return ((p << 10) | ((w << 5) | b));
}

You're right, it's so hard to do this...

[NickJohnson]

I didn't say there weren't alternatives, but those two things look similar, take the same amount of effort to understand, and produce exactly the same code (provided the compiler is good). Gotos are pretty much never better, but sometimes they are not worse.

Edit: My real point is that gotos have situations where they become a matter of taste rather than a matter of stability or maintainability. Nobody ever has to use them, but not all gotos should be bashed without consideration. I would have posted a heavily nested loop as an example of a proper goto, except that heavily nested loops are far worse than gotos imho.

[Brynet-Inc]

Wouldn't it make sense to just return to the caller when an error occurs? have that function handle them?

[NickJohnson]

Wouldn't it make sense to just return to the caller when an error occurs? have that function handle them?

No, because that would create duplication of process all over the place. The function is supposed to panic (or fix itself by killing processes, which I'm working on doing) on failure anyway, so having each caller panic independently would be really messy in comparison.

Edit: Also, I'm the one evangelizing gotos in this conversation, and I only have about five of them in *all the code I've ever written* - I just don't like when people give an absolute view about something, like "all gotos are bad".

[tantrikwizard]

Wouldn't it make sense to just return to the caller when an error occurs? have that function handle them?

Not in the case of my algorithm. Alloc is expected to return a valid chunk unless there is no memory.

[Solar]

When I have to debug an algorithm, and can't find the bug right away, one of my usual procedures is to write down the algorithm as NSD (Nassy-Shneiderman diagram), or a flowchart, because I usually find the bug while "translating" from C/C++ to NSD / flowchart.

Except when there are breaks, continues, or gotos in the code, because they make a fine mess out of a flowchart, and are plain impossible to translate into NSD.

I agree that, in certain tight situations, a goto (or a break, or a continue) can be the "fast way out", saving time and effort when you already have half the algorithm done before you realize you took a wrong turn earlier. I also agree that they can be efficient, and not-too-bad, if well-placed.

But they are just too easy to get wrong, and only an algorithm without them has real beauty.


{ahem}

What was the topic, again?

[tantrikwizard]

<snip>...Also, I'm the one evangelizing gotos in this conversation, and I only have about five of them in *all the code I've ever written* - I just don't like when people give an absolute view about something, like "all gotos are bad".

Ditto. There's probably a total of 10 in my entire repository. My particular coding style is to do as much as possible in as little code as possible. The less my eye has to scan through the better especially when trying to nail down bugs. This algorithm can easily be rewirtten to avoid them but its more intuitive to me in this situation where multiple threads are modifying a shared resource simultaniously. Screw it, I'll rewrite it in assembler and chalk it full of jmp statements. Using jmp statements in ASM wont get you shunned.

[Combuster]

<counter religious argument>

Watch out!...
http://xkcd.com/292/

Real programmers aren't afraid of raptors. They are wise enough to know they're extinct

[manonthemoon]

Code: Select all

uint32_t pool_alloc(pool_t *pool) {
   inline void full() {
      printk("%x\n", pool_query(pool));
      panic("pool allocator full");
      return 0;
   }
   <snip>
}

You're right, it's so hard to do this...

Umm.... nested functions are illegal in C and C++. So yeah, it is so hard to do that. More details.

Listen: any properly designed system NEVER has to use gotos. Ever. Any competent programmer can think in such purely logical terms that such erratic logic as jumping from one point to another doesn't even come to mind while programming.

You'd better scrub your code of any "break" or "continue" statements, because these are essentially "goto" without a label.

[NickJohnson]

Umm.... nested functions are illegal in C and C++. So yeah, it is so hard to do that. More details.

In *standard* C/C++. Works fine in GNU C though, which many of us are using. But, as I pointed out, there's no difference between nested functions and gotos except for part of the lexical scoping.

I actually ended up swapping out that section for a separate static inline function, because I found a way of combining some other similar error handlers with it. Now I've actually got no gotos at all, ironically.

[xvedejas]

I actually ended up swapping out that section for a separate static inline function, because I found a way of combining some other similar error handlers with it. Now I've actually got no gotos at all, ironically.

I think it's good practice to factor code out like this as much as sanely possible. It makes everything more abstract and palatable.

[neon]

I have never found a need to use goto. Ever. If a need arises where it would be useful, I consider the function is doing more then it is supposed to do and break it into smaller routines.

In languages where it is required by syntax (like old-school BASIC or its assembly language ancestor, jmp) its usage is fine. But in a structured language? Just dont ever see the use of them. All code that contains them can be written (usually better) without them.

Just my 2 cents

[Sly]

Well, a lot of the time, it's laziness in a high-level language. But sometimes, maybe in the middle of a nested loop, it can be useful. And of course, in languages where it is required. I personally think it is a great, powerful keyword. The problem with it is abuse.

[tantrikwizard]

7: ... and behave
No flaming. No spamming or advertising. No obscenities. Do not provoke fights. Trolls should live underground without internet. Windows vs linux and programming language battles have been fought many times and resulted every single time in a draw. Don't be tempted to try it.

5: Stay on topic
Simple: if you want to talk about something different, open a different thread. If you can't talk about the subject, don't post.

With all due respect, lets put this goto nonsense to sleep or start a new thread about it. If anyone has anything constructive about this algorithm (other than your personal dislikes of the flow) please respond, else please begin a new 'i hate gotos and youre evil if you use them' thread.

[gravaera]

EDIT: @tantrikwizard: I had just typed me up a beautiful discourse on the evils of gotos, with witty little detours, and intellectually engaging points. Great timing.

But anyway, @OP: You'll find that you'll probably get more help if you provide a real synopsis of the AREa where you think you need pointers. you just came and dumped code and expected us to figure out it intricacies. Why not post a smaller snippet with something more specific to ask?