User: Password:
Subscribe / Log in / New account

About Future CPUs

About Future CPUs

Posted Jan 23, 2012 9:24 UTC (Mon) by ekj (guest, #1524)
In reply to: About Future CPUs by XERC
Parent article: Denial of service via hash collisions

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.

(Log in to post comments)

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.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds