Lack of bit field instructions in x86 instruction set because of patents ?

Well, his imagination is a BIT larger than others...

ds

Single bit "fields" are totally inadequate, and the x86 instructions rather more so.

Mitch

Totally inadequate *FOR WHAT*? Why are the instructions you propose better than shift and mask?

-hpa

Simple answer:

One is CISC, and the other is RISC.

The IBM 7030 computer, STRETCH, made out of discrete transistors, had bit field instructions.

But most computers don't. The IBM 360 didn't. The x86 architecture started out from the 8086, a 16-bit architecture built to look as much like an 8-bit 8080 as possible... and so when it grew, it added the most important and popular operations, like floating-point arithmetic. Bit-field operations are regarded as very special-purpose.

John Savard

It could have been Motorola. Or it could have been Intel and Digital Research. Oh, there _was_ a CP/M 68K, but that would have been very unlikely...

Anyways, there *was* the Macintosh. Apple, not IBM, is at fault for playing its cards so badly as to hand Microsoft the Windows monopoly.

John Savard

Yes, they did, and it was not necessarily a big mistake.

Apple DID make a HUGE mistake, however, by price point alone.

That mistake will be their curtain call in this economy. I would not be buying Apple stock any time soon.

Intel had their own OS called ISIS back then. It was used on there

ISIS also did a fairly cute thing on its command line parsing. It only parsed the name of the program to be run and ran it. It left the :CI: (stdin) pointing on the line just after the name. The meant that if you redirected the input to a file, it was easy to implement IF functions etc for script files.

The passing of parameters to script files was a little clunky but it worked. The whole file was processed and the parameters were inserted making a new file that was then used as the input to the command line code.

elds

Obviously to make an efficient Intercal compiler, the machine should have a native Interleave instruction.

It's not an important example and almost certainly doesn't support your case anyway. For one thing, Huffman decoding is probably limited by memory bandwidth and not CPU speed. More importantly, though, any really complex instruction would either be implemented in microcode or would do something really awful to the pipeline, resulting in a huge performance hit for every other workload.

You mention bandwidth.

You mention the program being limited by bandwidth.

That more or less proves my point.

Many computers programs nowadays use 8 bits, 16 bits, 32 bits where maybe only 24 bits where needed or 23 bits, or 22 bits or whatever.

Nowadays these programs might be wasting bandwidth by using too much space for the storage:

Examples:

var DataArray : array[0..100000000000000000000000] of integer;

versus:

var DataArray : array[0..100000000000000000000000] of 22 bits;

The ammount of bandwidth savings and therefore speed gains is left as an exercise for the reader ! ;)

Bye, Skybuck.

Skybuck,

Yeah, and they might not be. Go look up some classic CISC vs. RISC history -- adding more instructions pretty much always makes you give up something else, and while just adding a few bit-oriented instructions is not going to be that significant, you can really get carried away to the point where your assembly language is almost as fancy as something like C, at which point performance almost always suffers.

Also keep in mind that when the 8086 was designed, memory was pretty much as fast as the CPU itself... although it cost of a lot of money. These days, memory is dirt cheap... but it's hundreds of times slower than the CPU core.

---Joel

I doubt it is for patent reasons. The DEC VAX had bit field instructions also.

luxury. (of MUL and DIV)

Hm! And when I started (pre Z80, and Bill and the Steves were were playing with trains) there wasn't ADD or SUBTRACT either; arithmetic was in BCD and all math was by table look-up for ADD and SUBTRACT and subroutines using these for MUL and DIV; the screen was an oscilloscope and the keyboard a teletype.

On the other hand... *addressing* the data might cost you more than the memory-to-CPU bandwidth savings would pay for.

Indexing an array which is word-wide (or byte-wide or doubleword-wide) is usually very fast. At worst you can convert from an array-index to a memory-offset simply by shifting the value left or right by one or two bits... an extremely fast operation. In some cases, CPUs will do the necessary shifting for you as part of the load/store instruction.

For dealing with "packed" arrays of odd lengths, such as you are suggesting, the index-to-address calculation is often very much more expensive. If you want to access 21-bit data items through a "load the right word(s) and extract the bits" methodology, then you need to be able to convert each array index into:

Memory word index Starting bit Ending bit and then load one or two words from memory and do the bitfield-extract based on the computed bit numbers.

This turns out to be an expensive operation, as it will typically require at least a multiply operation... which on many processors is significantly slower than a shift. It may also require a divide or modulus... and these can be even slower.

If your're lucky enough to be accessing your array sequentially most of the time, you may be able to optimize some of the sequential operations to avoid the need to multiply, and you may gain a performance advantage in these cases.

However, if you're mostly random accesses to the array, then you're unlikely to avoid many memory accesses by packing the array, and the cost of doing the multiply-and-mask/modulus operation for the index math may very well cost you more cycles than the few you'll save on hitting the same memory location twice.

Oh... reaching back to your original question as to why the X86 instruction set doesn't have a powerful set of arbitrary-bitfield manipulation instructions... I'd put it down to the following factors:

- Intel has always favored backwards-compatibility in their instruction set. They don't like making incompatible changes, and haven't had terribly good luck in the market when they did try (read up on the IA-84/Itanium architecture and its instruction set, which did *not* achieve great market success).

- The X86 instruction set architecture has its roots back in the days of much simpler processors, with far lower silicon density than is available today.

- In the terms of those days and silicon processes, the sort of arbitrary-bitfield manipulation instructions you are asking about were quite expensive. They require doing both a programmable bit-shift, and a programmable masking operation, each of which requires quite a lot of gates (again, by the standards of that era) and thus a lot of square area on the CPU chip.

- These instructions would probably require duplicating a significant amount of silicon logic which would already exist for other purposes (e.g. for the shift instructions). Re-use might not be possible. I believe that at the time these CPUs were invented, the designers felt that they had better uses for their available silicon-space and power budget. The feature you're asking for was simply not used enough to win the battle for silicon space.

The silicon-area/complexity equation has changed a lot since then, of course, and is probably not a factor at all these days. Concern about breaking backwards compatibility, or a desire to use the limited amount of previously-unused X86 instruction set space for other purposes of greater benefit (e.g. adding MMX and the like) is probably more of a factor.

Hmm... somehthing like the old IBM CADET -- "Can't Add, Doesn't Even Try?"

Huffman is a perfect example, we used to have poster here that would come back every few months with some imagined need for a multi-bit extraction opcode, and each and every time I was able to show portable code (C) that would do the same thing, and be faster:

For Huffmann it is actually quite simple:

If you have many short tokens (which you hope for, otherwise Huffman is a bad choice, right?), then a table-driven approach can average more than one token per iteration, by looking up the next N bits and extract one or more tokens.

For those very long, but also very rare tokens, you use multiple table levels.

I happen to know that this particular method works very well, since I used it when writing/optimizing the world's fastest ogg vorbis decoder. :-)

BTW, in Vorbis I never get more than one token, but it is still plenty fast enough, with most branch instruction predicting very well, particularly in 64-bit mode. This is due to having 64 bits in the decode buffer, so I can run many iterations of the decoder between each refill of that register.

Terje

Even without cache, DDR2 peak memory bandwidths of 6400 MB/s are readily acheivable for sequential reads. Assuming a 3 GHz single core might eat 6000 MB/s in instructions and 6000 MB/s in data, the speed ratio is hardly in the hundreds. With typical locality largly absorbed (maybe 75%) in cache, the required memory bandwith is not more than 6000 MB/s peak and 3000 MB/s sustained. Nicely within the available speed of current memory.

I was reading along expecting the Intel 432 to be mentioned... and you came up with the Itanium. Oh well, possible better known.

Cheers,

Steve N.