Solve a Debate

[castironpi at gmail.com]

On Feb 17, 7:05 am, Wolfgang Draxinger <wdraxin... at darkstargames.de>
wrote:
> 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: hexar... at jabber.org, ICQ: 134682867

m - 2 and 30 + bool(1 << m & 5546) or 28
sub x' x 2
cjump x' 0 $but_28
shift x'' 1 x
and x'' 5546
cjump x'' 0 $not_31
add x'' 1
$not_31:
add x'' 30
cjump x'' 0 $but_28
assign $days x''
jump $end
$but_28:
assign $days 28
jump $end
$end:

22 blups, 4, 9, 10, 12, or 13 ticks.