About Future CPUs [LWN.net]

About Future CPUs

Posted Jan 23, 2012 1:09 UTC (Mon) by XERC (guest, #14626)
Parent article: Denial of service via hash collisions

If there are graphics accelerators, which nowadays are integrated with the CPU chip, then why can't there be text accelerators for web servers and alike?

For example, there might be some sort of a CPU instruction that is specially meant for hardware based sorting of integers in a given memory range. The instruction can impose a requirement that the memory range is small enough to fit the CPU's L1 cache and the maximum value for the memory region size might be available with one other CPU instruction.

If graphics cards were inserted to PC-s as an add-on, then the web servers could use some text-cards that use hardware based sorting for UTF-8 text. Some open-source, system-wide, C library might just abstract away the hardware so that PC-s that don't have the special hardware, do it on the main CPU and everyone would be happy.

After all, that's how historically the floating point arithmetic got integrated to the main CPU and that's how the graphics accelerators (GPU-s) got integrated with the most modern CPU chips.

Given the popularity of hash-tables in modern programming languages, hardware support for some seed based, not necessarily cryptographically suitable, hash function is also pretty welcome. After all, CPU-s are for running software, not the other way around.

(Log in to post comments)

About Future CPUs

Posted Jan 23, 2012 9:24 UTC (Mon) by ekj (guest, #1524) [Link]

Sorting integers is O(n). It's just the general sorting-problem, where your operations are limited to compare() and swap() which has n*log n as a lower bound.

The problem isn't that sorting is heavy work, it typically isn't.

The problem is that with certain pathological input (malicious attacks) sorting dict-insertion and dict-lookup can be very much slower than expected.

This can be avoided with different choice of hash-function for the dictionary, but that will tend to be slower for the typical (non-malicious) case.

Putting the thing in hardware wouldn't really change that.

Actually it will

Posted Jan 23, 2012 12:30 UTC (Mon) by khim (subscriber, #9252) [Link]

Putting the thing in hardware wouldn't really change that.

But it would! Good hash functions are pretty hard to implement in software because you basically need to randomly shuffle bits around - and it's hard to do that in software. In hardware it's trivial.

AES-NI instructions have sustained speed of about 1byte/tick (of course small strings are slower). It'll be interesting to see how large of a hit it'll produce in python, for example. It will probably be slower then current hash, but difference may be small enough for real usage.

Actually it will

Posted Jan 23, 2012 12:40 UTC (Mon) by ekj (guest, #1524) [Link]

I guess I was being unclear.

What I meant is that in typical use, producing hashes to use for inserting and/or looking things up in dictionaries is not a major performance-impact for Python.

I don't doubt that hashes can be produces quicker by dedicated hardware, but if you're using a small fraction of your time for that purpose to start with, then the gains from reducing it, are modest.

It'd be interesting benchmarking a variety of workloads in a variety of languages to see what fraction of time is used for hashing though, because I'm really just guessing here, and I could be wrong.