Scenario 3 wouldn't infringe, because the reference there isn't a symbolic
one, it's direct use of the address with no symbol involved. If it infringed,
then the 8080 instruction set itself infringes on the patent because it has
instructions in it with the address directly contained in the instruction. But
the 8080 pre-dates the patents in question by decades, so it's impossible for it
to infringe on those patents.
Scenarios 1 and 2 both would infringe.
What's in the code is the name (directly or indirectly), and you have to look up
the name and translate it into an address before it can be used. Obvious Dalvik
can't infringe on that, because it can't contain strings in the instructions
either directly or indirectly. The case Oracle's trying to pull in though
involves the use of numbers, not strings, as symbols. Which is entirely
legal, all a 32-bit integer is is a fixed-length 4-character string (assuming an
8-bit char). In that case we'd just have scenario 1, with the value in the
instruction being used as the key to search for in the symbol table (tree).
Notice that the value stored in the instruction can't itself be directly used to
access data, you need to take it and translate it into an address via the symbol
table before you've got something you can use to access data.
Dalvik
though uses scenario 3 and another one, scenario 4: the symbol table is
implemented as an array with each slot in the array holding the address needed
to access that particular symbol's data, and symbol names are made to be small
integers corresponding to the index in the array of the slot assigned to that
symbol. Now instead of doing a search of a binary tree, I can just index into
the symbol table to find the address corresponding to a name. But wait a moment,
modern hardware supports indexed indirect addressing. In C it'd be written as
"*(symbol_table[name])": start at the address pointed to by symbol_table, add
the value of name times the width of an array element to index into the table,
take the pointer found there and dereference it to get the data. Notice that
this can be done in one instruction, the syntax varies slightly in assembly but
that construction's a legal x86 machine-language operand. Notice now that I've
eliminated the entire process of looking the name up in the symbol table. I've
gone and turned the use of a symbolic reference into direct addressing of
memory. By careful choosing of the symbol's name, I've effectively made it's
name it's actual address. Which of course isn't a symbolic reference at all, and
gives you worlds of performance gains because you aren't doing all those
symbol-table lookups anymore.
TRS-80 BASIC was my first introduction to
this trick. Each variable reference was prefixed with an initially-blank index
into the variable table. The first time the line executed the variable name
would be looked up in the variable table and the index value filled in. After
that, if the index value was filled in the interpreter could use it to go
directly to the correct slot in the variable table without having to do the name
lookup again (and on a 1.77MHz 8-bit Z-80, doing a linear search and string
compares wasn't fast so this was a big performance win). The only difference
between this and what Oracle's claiming is that Oracle's interpreting virtual
machine instructions and TRS-80 Model 1 BASIC was interpreting a tokenized BASIC
program without any virtual machine. [ Reply to This | Parent | # ]
|
