On Jan 2 2012, Ivan Raikov wrote:
I also do not understand why using different data structures is not
under consideration.
This might be a matter of taste wrt. maintaining software.
I prefer to choose data structures for their merits.
When it turns out that the _implementation_ is (kind
On Dec 31 2011, John Cowan wrote:
Thomas Bushnell, BSG scripsit:
Huh? The point is that well-chosen hash collisions can force the
algorithm into its worst case behavior, and if that's linear, it's a
problem. Choosing a linear algorithm to begin with is hardly a win!
Let me second that one.
On Sun, Jan 01, 2012 at 01:08:39PM +0100, Jörg F. Wittenberger wrote:
On Dec 31 2011, John Cowan wrote:
Huh? The point is that well-chosen hash collisions can force the
algorithm into its worst case behavior, and if that's linear, it's a
problem. Choosing a linear algorithm to begin with is
Peter Bex scripsit:
Agreed. Changing datastructures is not an option.
Why not? It's a matter of replacing a datastructure whose worst-case
cost is quadratic with one whose worst-case cost is linear. Do we even
know what the break-even point is between a-lists with their higher
algorithmic
On Sun, Jan 01, 2012 at 09:57:15AM -0500, John Cowan wrote:
Peter Bex scripsit:
Agreed. Changing datastructures is not an option.
Why not?
Because not fixing hash tables makes them into another footgun.
Also because fixing them transparently is simple and has almost
zero overhead.
It's
Peter Bex scripsit:
Yes, and doing it in *every* *freaking* program. Including
third-party libraries written long ago or by people assuming a sane
srfi-69 implementation (or more likely, not having thought about it).
Not at all. Only fixing programs that are exposed to potentially
malicious
On Sun, Jan 01, 2012 at 10:29:18AM -0500, John Cowan wrote:
Peter Bex scripsit:
Yes, and doing it in *every* *freaking* program. Including
third-party libraries written long ago or by people assuming a sane
srfi-69 implementation (or more likely, not having thought about it).
Not at
On Sun, Jan 01, 2012 at 04:36:41PM +0100, Peter Bex wrote:
On Sun, Jan 01, 2012 at 10:29:18AM -0500, John Cowan wrote:
Peter Bex scripsit:
Yes, and doing it in *every* *freaking* program. Including
third-party libraries written long ago or by people assuming a sane
srfi-69
I also do not understand why using different data structures is not
under consideration. There are many algorithms and data structures for
handling collisions so that hash table access remains efficient even with a
high rate of collisions. Why not have the option to choose the data
structure
Hi all,
I never thought about that one, but it could be a real issue.
Julian Wälde and Alexander Klink reporting:
http://www.nruns.com/_downloads/advisory28122011.pdf
I have not figured whether or not chicken would be vulnerable.
Anybody able to do so?
Best regards
/Jörg
Jörg F. Wittenberger scripsit:
I have not figured whether or not chicken would be vulnerable.
Anybody able to do so?
A simple and adequate resolution would be to discard the use of a
hashtable in this case in favor of an a-list, so that there is no
possibility of a hash collision.
--
John
Thomas Bushnell, BSG scripsit:
Huh? The point is that well-chosen hash collisions can force the algorithm
into its worst case behavior, and if that's linear, it's a problem.
Choosing a linear algorithm to begin with is hardly a win!
But it's worst-case as well as best-case linear. From the
12 matches
Mail list logo