Solve a Debate

[Wolfgang Draxinger]

nexes wrote:

> there is more data that needed to be assigned(i.e. a couple
> megs of data) it would be simpler (and more efficient) to
> do a compare rather then assigning all that data to an array,
> since you are only going to be using 1 value and the rest
> of the data in the array is useless.

Ouch, you're hurting my brain...

Okay, let's state this first: A lookup table IS the more
efficient solution.

Somehow you seem to think, that a lookup table will require more
resources (memory I guess you thought) than a sequence of
comparisons. However you didn't take into account, that the
program code itself requires memory, too (for the operation
codes). For the sake of simplicity let's assume, that every
operation code and every variable takes exactly one "blurp" of
memory (what a blurp is exactly we leave undefined here, it's
just the smallest unit of memory our hypothetically machine can
process).

Let's also assume, that you can pack everything, that happens in
a operation into a single opcode, which by definition fits into
a blurp: In case of a comparision this would include the value,
to operand to compare to and where to jump if the comparision
satisfies. Assignment is a own operation, thus it doesn't go
into the compare operation (it would be rather inefficient to
try to fit all possible things you do after a comparision into a
huge variety of comparision opcodes).

In the following example each line should be considered as a
single operation. And let's assume that every operation takes one
tick to execute. Labels take no memory. A table is a label with
a number of values following. The label of the table itself
doesn't consume memory either, however a compiler/assembler
might decide to insert a relative jump just before the table so
that the program doesn't run into it.

The operations are like this:

compare $variable $value $jump_label

assign $variable $value | $table[$index]

jump $jump_label

$jump_label:

$table $number_of values:
$value
$value
...

The shortest compare/assign program for the month problem would
look like this

compare month 1 month_31
compare month 2 month_28
compare month 3 month_31
compare month 4 month_30
...
compare month 11 month_30
compare month 12 month_31
month_30: assign $days 30
jump end
month_31: assign $days 31
jump end
month_28: assign $days 28
end:

This program consists of 12+5 = 18 operations. There are no
tables, to the program consumes only those 18 blurps. Running
time is between 3 and 14 ticks. 

Now let's have a look on the table based variant

days_in_month 12:
31
30
28
31
...
30
31
assign $days days_in_month[$month]

This program consists of 2 operations (table jump and assignment)
and 12 values. This makes a memory consumption of 12+2 = 14
blurps. Running time is always 2 ticks. You see that the table
based approach both takes less memory (14 blurbs vs. 18 blurps)
and always runs faster (2 ticks vs. 3...14 ticks) than the
comparison/jump/assignment based solution.

And that was just this artificial example. In most real world
applications the operands to a comparision would take additional
memory, at it's best the opcode would also address some
register(s), but not more, so this would also add the
instructions to fill the registers with the values.

Now you might want to state the above examples are indeed
artificial. But OTOH they're not so artificial then again. Most
assembler code works that way and if you take the AVR
architecture it almost looks that way there. And if you're
thinking of Python you can bet, that an opcode will not contain
all information, but have the operands encoded in additional
values, consuming memory.

Look up Table is more efficient: Debate solved.

Wolfgang Draxinger
-- 
E-Mail address works, Jabber: hexarith at jabber.org, ICQ: 134682867