On Tue, Mar 13, 2007 at 11:08:27AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Tuesday 13 March 2007 10:32, Evgeniy Polyakov wrote:
> > On Fri, Mar 02, 2007 at 11:52:47AM +0300, Evgeniy Polyakov
> ([EMAIL PROTECTED]) wrote:
> > So, I ask network developers about testing environment for so
On Tuesday 13 March 2007 10:32, Evgeniy Polyakov wrote:
> On Fri, Mar 02, 2007 at 11:52:47AM +0300, Evgeniy Polyakov
([EMAIL PROTECTED]) wrote:
> So, I ask network developers about testing environment for socket lookup
> benchmarking. What would be the best test case to determine performance
> of
On Fri, Mar 02, 2007 at 11:52:47AM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
> So I get my words about tree/trie implementation instead of hash table
> for socket lookup back.
Hmm, I was a bit fast to draw a line, there are some possibilities to
have faster than hash table lookup using
On Sun, Mar 04, 2007 at 02:02:36AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> On 3/3/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
> >Btw, you could try to implement something you have written above to show
> >its merits, so that it would not be an empty words :)
>
> Before I implem
Michael K. Edwards writes:
> This, incidentally, seems very similar to the process that Robert
> Olsson and Stefan Nilsson have gone through with their trie/hash
> project. Although I haven't tried it out yet and don't have any basis
> for an independent opinion, the data and analysis provid
On 3/4/07, David Miller <[EMAIL PROTECTED]> wrote:
From: "Michael K. Edwards" <[EMAIL PROTECTED]>
> Before I implement, I design. Before I design, I analyze. Before I
> analyze, I prototype. Before I prototype, I gather requirements.
How the heck do you ever get to writing ANYTHING if you wor
From: "Michael K. Edwards" <[EMAIL PROTECTED]>
Date: Sun, 4 Mar 2007 02:02:36 -0800
> On 3/3/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
> > Btw, you could try to implement something you have written above to show
> > its merits, so that it would not be an empty words :)
>
> Before I implemen
On 3/3/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
Btw, you could try to implement something you have written above to show
its merits, so that it would not be an empty words :)
Before I implement, I design. Before I design, I analyze. Before I
analyze, I prototype. Before I prototype, I
On Fri, Mar 02, 2007 at 12:45:36PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> On 3/2/07, Eric Dumazet <[EMAIL PROTECTED]> wrote:
> >Thank you for this report. (Still avoiding cache misses studies, while they
> >obviously are the limiting factor)
>
> 1) The entire point of going to a
On 3/2/07, Eric Dumazet <[EMAIL PROTECTED]> wrote:
Thank you for this report. (Still avoiding cache misses studies, while they
obviously are the limiting factor)
1) The entire point of going to a tree-like structure would be to
allow the leaves to age out of cache (or even forcibly evict them)
On Fri, Mar 02, 2007 at 10:56:23AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Friday 02 March 2007 09:52, Evgeniy Polyakov wrote:
>
> > Ok, I've ran an analysis of linked lists and trie traversals and found
> > that (at least on x86) optimized one list traversal is about 4 (!)
> > times
On Friday 02 March 2007 09:52, Evgeniy Polyakov wrote:
> Ok, I've ran an analysis of linked lists and trie traversals and found
> that (at least on x86) optimized one list traversal is about 4 (!)
> times faster than one bit lookup in trie traversal (or actually one
> lookup in binary tree-like st
On Sat, Feb 17, 2007 at 04:13:02PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
> > >I noticed in an LCA talk mention that apprently extensible hashing
> > >with RCU access is an unsolved problem. Here's an idea for solving it.
> > >
> >
> > Yes, I have been playing around with the sam
On 22 Feb 2007 18:49:00 -0500, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
The rehash-every-10-minutes detail is theoretically unnecessary,
but does cover the case where a would-be attacker *does* get a chance
to look at a machine, such as by using routing delays to measure the
effectiveness of
> I think you misunderstood me. If you are trying to DoS me from
> outside with a hash collision attack, you are trying to feed me
> packets that fall into the same hash bucket. The Jenkins hash does
> not have to be artifact-free, and does not have to be
> cryptographically strong. It just has
On Thu, 22 Feb 2007 03:07:55 -0800 (PST)
David Miller <[EMAIL PROTECTED]> wrote:
> From: "Michael K. Edwards" <[EMAIL PROTECTED]>
> Date: Thu, 22 Feb 2007 03:00:32 -0800
>
> > Besides, RCUing a hash of any sort sounds like a nightmare, whereas
> > something like a splay tree is reputed to be very
From: Andi Kleen <[EMAIL PROTECTED]>
Date: Thu, 22 Feb 2007 12:41:05 +0100
> > With 100k flows we typically see an aver depth 1.3 and a max depth 4.
> > Right
>
> This includes full srcport:dstport?
Yes.
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a mess
> With 100k flows we typically see an aver depth 1.3 and a max depth 4. Right
This includes full srcport:dstport?
> now there is only a dst entry in leaf nodes. So yes anything else we can put
> in leaf is "free".
How much would fit there?
-Andi
-
To unsubscribe from this list: send the l
From: "Michael K. Edwards" <[EMAIL PROTECTED]>
Date: Thu, 22 Feb 2007 03:00:32 -0800
> Besides, RCUing a hash of any sort sounds like a nightmare, whereas
> something like a splay tree is reputed to be very straightforward to
> make "persistent" in the functional-programming sense. I haven't
> co
On 2/22/07, David Miller <[EMAIL PROTECTED]> wrote:
From: "Michael K. Edwards" <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2007 13:15:51 -0800
> it had better be a 2-left hash with a compact
> overflow pool for the rare case of second collision.
Just like Evgeniy, you should do your research too :-))
From: "Michael K. Edwards" <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2007 13:15:51 -0800
> it had better be a 2-left hash with a compact
> overflow pool for the rare case of second collision.
Just like Evgeniy, you should do your research too :-
The gain for multiple-hash schemes, such as 2-left
Robert Olsson a écrit :
David Miller writes:
> But what about if tree lookup were free :-)
>
> This is why I consider Robert Olsson's trash work the most promising,
> if we stick sockets into his full flow identified routing cache trie
> entries, we can eliminate lookup altogether.
>
>
David Miller writes:
> But what about if tree lookup were free :-)
>
> This is why I consider Robert Olsson's trash work the most promising,
> if we stick sockets into his full flow identified routing cache trie
> entries, we can eliminate lookup altogether.
>
> Just like how he already
Look, Evgeniy. Eric and I may be morons but davem is not. He's
telling you, again and again, that DoS attacks do happen, that to
survive them you need for the distribution of tuples within hash
buckets to vary unpredictably from system to system and boot to boot,
and that XOR hash does not accom
From: Eric Dumazet <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2007 14:19:30 +0100
> Now, when the rate of lookups/inserts/delete is high, with totally random
> endpoints and cache *always* cold , 'tree structures' are not welcome (not
> cache friendly)
But what about if tree lookup were free :-)
Th
On Wednesday 21 February 2007 13:41, Andi Kleen wrote:
> Eric Dumazet <[EMAIL PROTECTED]> writes:
> > For example, sock_wfree() uses 1.6612 % of cpu because of false sharing
> > of sk_flags (dirtied each time SOCK_QUEUE_SHRUNK is set :(
>
> Might be easily fixable by moving the fields around a bit?
Eric Dumazet <[EMAIL PROTECTED]> writes:
>
> For example, sock_wfree() uses 1.6612 % of cpu because of false sharing of
> sk_flags (dirtied each time SOCK_QUEUE_SHRUNK is set :(
Might be easily fixable by moving the fields around a bit?
> If we want to optimize tcp, we should reorder fields to
From: Evgeniy Polyakov <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2007 12:51:09 +0300
> Linux route cache does not change $c (third parameter), and it _seems_
> that distribution for the random $a and $b is fair, while when $c is
> formed over attacker's data, random per-boot $initval does not help.
I
On Wed, Feb 21, 2007 at 10:38:22AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Wednesday 21 February 2007 10:27, Evgeniy Polyakov wrote:
> > On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED])
> wrote:
> > > On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrot
On Wed, Feb 21, 2007 at 01:34:40AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
> > I repeat again - add your salt into jenkins hash and I will show you
> > that it has the same problems.
> > So, I'm waiting for your patch for jhash_*_words().
>
> The problem is that whilst XOR, with arbitrary
On Wednesday 21 February 2007 10:27, Evgeniy Polyakov wrote:
> On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
> > > I shown that numbers 4 times already, do you read mails and links?
> > > Did you s
From: Evgeniy Polyakov <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2007 11:56:08 +0300
> On Tue, Feb 20, 2007 at 12:09:59PM -0800, Michael K. Edwards ([EMAIL
> PROTECTED]) wrote:
> > On 2/20/07, Michael K. Edwards <[EMAIL PROTECTED]> wrote:
> > >Correct. That's called a "weak hash", and Jenkins is kno
On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
> > I shown that numbers 4 times already, do you read mails and links?
> > Did you see an artifact Eric showed with his data?
> >
>
> I showed all your
On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
> I shown that numbers 4 times already, do you read mails and links?
> Did you see an artifact Eric showed with his data?
>
I showed all your thinking is wrong.
Some guys think MD5 checksum is full of artifacts, since its certainly
pos
On Tue, Feb 20, 2007 at 12:09:59PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> On 2/20/07, Michael K. Edwards <[EMAIL PROTECTED]> wrote:
> >Correct. That's called a "weak hash", and Jenkins is known to be a
> >thoroughly weak hash. That's why you never, ever use it without a
> >salt,
On Tue, Feb 20, 2007 at 12:03:04PM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> >I just shown a problem in jenkins hash - it is not how to find a
> >differnet input for the same output - it is a _law_ which allows to
> >break a hash. You will add some constant, and that law will be turne
On 2/20/07, Michael K. Edwards <[EMAIL PROTECTED]> wrote:
Correct. That's called a "weak hash", and Jenkins is known to be a
thoroughly weak hash. That's why you never, ever use it without a
salt, and you don't let an attacker inspect the hash output either.
Weak in a cryptographic sense, of
On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
How I like personal insults - it is always fun to read about myself from
people who never knew me :)
On this occasion, I did not set out to insult you. I set out to
suggest an explanation for why cooler and grayer heads than mine are
not
On Tue, Feb 20, 2007 at 08:17:31PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> I shown your test was bogus. All your claims are just bogus.
> I claim your 'true random data' is a joke. rand() in your program is a pure
> joke.
Care to reread your mail about your true random case with hash ch
On Tue, Feb 20, 2007 at 11:13:50AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
> >And here are another ones which produce the same hash value.
> >Of course searching for pair for jhash('jhash is broken')
> >will require more steps,
All right, Eric, you and me so clevvah, let's embarrass our own selves
designing this thing in public instead of picking on poor Evgeniy.
Which would you rather RCU, a 2-left hash or a splay tree? 2-left
hash gets you excellent occupation fraction before the first real
collision, so you can be ut
On Tuesday 20 February 2007 20:06, Evgeniy Polyakov wrote:
> > I added to my 'simulator_plugged_on_real_server' the average cost
> > calculation, relative to number of cache line per lookup.
> >
> > ehash_size=2^20
> > xor hash :
> > 386290 sockets, Avg lookup cost=3.2604 cache lines/lookup
> > 39
On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
And here are another ones which produce the same hash value.
Of course searching for pair for jhash('jhash is broken')
will require more steps, but it is doable.
That means that if attacker has a full control over one host, it can
create a
On Tue, Feb 20, 2007 at 07:55:15PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Tuesday 20 February 2007 19:00, Evgeniy Polyakov wrote:
> > As you can see, jhash has problems in a really trivial case of 2^16,
> > which in local lan is a disaster. The only reason jenkins hash is good
> > for
On Tuesday 20 February 2007 19:00, Evgeniy Polyakov wrote:
> As you can see, jhash has problems in a really trivial case of 2^16,
> which in local lan is a disaster. The only reason jenkins hash is good
> for hashing purposes is that is it more complex than xor one, and thus
> it is harder to find
On Tue, Feb 20, 2007 at 08:55:50PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
> Here is a dump of possible addr/port pairs which end up badly
> distributed:
>
> 8e363a50:27652 -> c0a80001:20480
> 8e363a50:35529 -> c0a80001:20480
> 8e363a50:40919 -> c0a80001:20480
> 8e363a50:46720 -> c0a80
On Tue, Feb 20, 2007 at 06:53:59PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > > I've attached source code and running script.
> > > $ ./run.sh
> >
> > Yep, of course.
>
> Your test program is just bogus. artefacts come from your 'random' generator.
>
> You just increment a counter, assum
On Tue, Feb 20, 2007 at 06:20:26PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > Hmm, I've just ran following test:
> > 1. created 2^20 hash table.
> > 2. ran in loop (100*(2^20) iterations) following hashes:
> > a. xor hash (const_ip, const_ip, random_word)
>
> So what ? to attack me you w
On Tuesday 20 February 2007 18:05, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 07:59:07PM +0300, Evgeniy Polyakov
([EMAIL PROTECTED]) wrote:
> > I've attached source code and running script.
> > $ ./run.sh
>
> Yep, of course.
Your test program is just bogus. artefacts come from your 'random
On Tuesday 20 February 2007 17:59, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 05:38:19PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > > It is secrecy, not security - attacker will check the source and find
> > > where constant per-boot value is added and recalculate attack vector -
>
On Tue, Feb 20, 2007 at 07:59:07PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
> I've attached source code and running script.
> $ ./run.sh
Yep, of course.
--
Evgeniy Polyakov
#include
#include
#include
#include
#include
#include
#include
typedef unsigned int u32;
typede
On Tue, Feb 20, 2007 at 05:38:19PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > It is secrecy, not security - attacker will check the source and find
> > where constant per-boot value is added and recalculate attack vector -
> > we all were college students, it would be even more fun to crac
On Tuesday 20 February 2007 17:20, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 05:08:12PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > > Adding XOR with constant value does not change distribution.
> > > Variable salt will end up with differnet buckets for the same flow.
> > > It is fo
On Tue, Feb 20, 2007 at 05:08:12PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > Adding XOR with constant value does not change distribution.
> > Variable salt will end up with differnet buckets for the same flow.
> > It is forbidden - it is not the situation created for passwd/des decades
>
On Tuesday 20 February 2007 16:59, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 07:49:11AM -0800, Michael K. Edwards
([EMAIL PROTECTED]) wrote:
> > On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
> > >Jenkins _does_ have them, I showed tests half a year ago and in this
> > >thread too
On Tuesday 20 February 2007 16:49, Michael K. Edwards wrote:
> On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
> > Jenkins _does_ have them, I showed tests half a year ago and in this
> > thread too. Actually _any_ hash has them it is just a matter of time
> > to find one.
>
> I think you m
On Tue, Feb 20, 2007 at 07:49:11AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
> >Jenkins _does_ have them, I showed tests half a year ago and in this
> >thread too. Actually _any_ hash has them it is just a matter of time
> >to fi
On 2/20/07, Evgeniy Polyakov <[EMAIL PROTECTED]> wrote:
Jenkins _does_ have them, I showed tests half a year ago and in this
thread too. Actually _any_ hash has them it is just a matter of time
to find one.
I think you misunderstood me. If you are trying to DoS me from
outside with a hash coll
On Tue, Feb 20, 2007 at 07:07:16AM -0800, Michael K. Edwards ([EMAIL
PROTECTED]) wrote:
> On 2/20/07, David Miller <[EMAIL PROTECTED]> wrote:
> >Actually someone (I think it was Evgeniy in fact) made such
> >comparisons and found in his studies that not only does the current
> >ehash xor hash func
On 2/20/07, David Miller <[EMAIL PROTECTED]> wrote:
Actually someone (I think it was Evgeniy in fact) made such
comparisons and found in his studies that not only does the current
ehash xor hash function distribute about as well as jenkins, it's
significantly cheaper to calculate :-)
However, i
On Tue, Feb 20, 2007 at 12:25:23PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
wrote:
> And there is _no_ O(1) - O(1) is just a hash entry selection, then you
> need to add the whole chain path, which can be long enough.
> For example for the length 9 you have 1000 entries - it is exactly size
> o
On Tue, Feb 20, 2007 at 12:30:18PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Tuesday 20 February 2007 12:10, Eric Dumazet wrote:
> >
> > > Yep, it happend to be my tests :)
> > > Jenkins hash was slower and had significant artifacts for some usage
> > > cases ended up with extremely lon
On Tue, Feb 20, 2007 at 12:34:59PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > Getting into account that network stack with NAPI schedules several
> > packets to be queued into socket and all that happens without any
> > infuence from userspace, trie/tree wins again in that regard that
> >
On Tuesday 20 February 2007 12:29, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 12:09:51PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > If we want to optimize tcp, we should reorder fields to reduce number of
> > cache lines, not change algos. struct sock fields are currently placed to
On Tuesday 20 February 2007 12:10, Eric Dumazet wrote:
>
> > Yep, it happend to be my tests :)
> > Jenkins hash was slower and had significant artifacts for some usage
> > cases ended up with extremely long chain length.
> > One can find more details at
> > http://tservice.net.ru/~s0mbre/blog/2006
On Tue, Feb 20, 2007 at 12:09:51PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> If we want to optimize tcp, we should reorder fields to reduce number of
> cache
> lines, not change algos. struct sock fields are currently placed to reduce
> holes, while they should be grouped by related fiel
On Tue, Feb 20, 2007 at 12:10:22PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> Please explain why you choseh = jhash_2words(faddr, laddr, ports);
> h ^= h >> 16;
> h ^= h >> 8;
>
> jhash is very good, no need to try to be smarter, shufling some bytes... and
> adding arti
On Tuesday 20 February 2007 11:44, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 11:04:15AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > You totally miss the fact that the 1-2-4 MB cache is not available for
> > you at all. It is filled by User accesses. I dont care about DOS. I care
> >
On Tuesday 20 February 2007 11:30, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 02:12:09AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
> > From: Eric Dumazet <[EMAIL PROTECTED]>
> > Date: Tue, 20 Feb 2007 11:04:15 +0100
> >
> > > Using a jenkin's hash permits a better hash distribution for
On Tuesday 20 February 2007 11:12, David Miller wrote:
> From: Eric Dumazet <[EMAIL PROTECTED]>
> Date: Tue, 20 Feb 2007 11:04:15 +0100
>
> > Using a jenkin's hash permits a better hash distribution for a litle
> > cpu cost. I will post later a distribution simulation based on the
> > data gathere
On Tue, Feb 20, 2007 at 11:04:15AM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> You totally miss the fact that the 1-2-4 MB cache is not available for you at
> all. It is filled by User accesses. I dont care about DOS. I care about real
> servers, servicing tcp clients. The TCP service/stack
On Tue, Feb 20, 2007 at 02:12:09AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
> From: Eric Dumazet <[EMAIL PROTECTED]>
> Date: Tue, 20 Feb 2007 11:04:15 +0100
>
> > Using a jenkin's hash permits a better hash distribution for a litle
> > cpu cost. I will post later a distribution simulation
On Tue, Feb 20, 2007 at 01:57:45AM -0800, David Miller ([EMAIL PROTECTED])
wrote:
> > What you miss is the fact, that upper layers of the tree are always in the
> > cache. So its access cost nothing compared to every time new entry in
> > the hash table.
>
> It will not be on a real computer spen
From: Eric Dumazet <[EMAIL PROTECTED]>
Date: Tue, 20 Feb 2007 11:04:15 +0100
> Using a jenkin's hash permits a better hash distribution for a litle
> cpu cost. I will post later a distribution simulation based on the
> data gathered from the same real server.
Actually someone (I think it was Evg
On Tuesday 20 February 2007 10:25, Evgeniy Polyakov wrote:
> On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > On Monday 19 February 2007 16:14, Eric Dumazet wrote:
> > > Because O(1) is different of O(log(N)) ?
> > > if N = 2^20, it certainly makes a difference
From: Evgeniy Polyakov <[EMAIL PROTECTED]>
Date: Tue, 20 Feb 2007 12:25:23 +0300
> What you miss is the fact, that upper layers of the tree are always in the
> cache. So its access cost nothing compared to every time new entry in
> the hash table.
It will not be on a real computer spending reason
On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Monday 19 February 2007 16:14, Eric Dumazet wrote:
> >
> > Because O(1) is different of O(log(N)) ?
> > if N = 2^20, it certainly makes a difference.
> > Yes, 1% of chains might have a length > 10, but yet 99% o
Evgeniy Polyakov <[EMAIL PROTECTED]> writes:
>
> My experiment shows almost 400 nsecs without _any_ locks - they are
> removed completely - it is pure hash selection/list traverse time.
Are you sure you're not measuring TLB misses too? In user space
you likely use 4K pages. The kernel would use 2
On 19 Feb 2007 13:04:12 +0100, Andi Kleen <[EMAIL PROTECTED]> wrote:
LRU tends to be hell for caches in MP systems, because it writes to
the cache lines too and makes them exclusive and more expensive.
That's why you let the hardware worry about LRU. You don't write to
the upper layers of the
On Mon, Feb 19, 2007 at 01:26:42PM -0500, Benjamin LaHaise wrote:
> On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet wrote:
> > So even with a lazy hash function, 89 % of lookups are satisfied with less
> > than 6 compares.
>
> Which sucks, as those are typically going to be cache misses (c
On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet wrote:
> So even with a lazy hash function, 89 % of lookups are satisfied with less
> than 6 compares.
Which sucks, as those are typically going to be cache misses (costing many
hundreds of cpu cycles). Hash chains fair very poorly under Do
On Monday 19 February 2007 16:14, Eric Dumazet wrote:
>
> Because O(1) is different of O(log(N)) ?
> if N = 2^20, it certainly makes a difference.
> Yes, 1% of chains might have a length > 10, but yet 99% of the lookups are
> touching less than 4 cache lines.
> With a binary tree, log(2^20) is 20.
On Monday 19 February 2007 15:25, Evgeniy Polyakov wrote:
> On Mon, Feb 19, 2007 at 03:14:02PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > > Forget about cache misses and cache lines - we have a hash table, only
> > > part of which is used (part for time-wait sockets, part for established
>
On Mon, Feb 19, 2007 at 03:14:02PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > Forget about cache misses and cache lines - we have a hash table, only
> > part of which is used (part for time-wait sockets, part for established
> > ones).
>
> No you didnt not read my mail. Current ehash is n
On Monday 19 February 2007 14:56, Evgeniy Polyakov wrote:
> On Mon, Feb 19, 2007 at 02:38:13PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> > On Monday 19 February 2007 12:41, Evgeniy Polyakov wrote:
> > > > 1 microsecond ? Are you kidding ? We want no more than 50 ns.
> > >
> > > Theory again
Actually for socket code any other binary tree will work perfectly ok -
socket code does not have wildcards (except listening sockets), so it is
possible to combine all values into one search key used in flat
one-dimensional tree - it scales as hell and allows still very high
lookup time.
As of ca
On Mon, Feb 19, 2007 at 02:38:13PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> On Monday 19 February 2007 12:41, Evgeniy Polyakov wrote:
>
> > > 1 microsecond ? Are you kidding ? We want no more than 50 ns.
> >
> > Theory again.
>
>
> Theory is nice, but I personally prefer oprofile :)
> I
On Monday 19 February 2007 12:41, Evgeniy Polyakov wrote:
> > 1 microsecond ? Are you kidding ? We want no more than 50 ns.
>
> Theory again.
Theory is nice, but I personally prefer oprofile :)
I base my comments on real facts.
We *want* 50 ns tcp lookups (2 cache line misses, one with reader in
Andi Kleen writes:
> > If not, you loose.
>
> It all depends on if the higher levels on the trie are small
> enough to be kept in cache. Even with two cache misses it might
> still break even, but have better scalability.
Yes the trick to keep root large to allow a very flat tree and few
On Sun, Feb 18, 2007 at 09:21:30PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> Evgeniy Polyakov a e'crit :
> >On Sun, Feb 18, 2007 at 07:46:22PM +0100, Eric Dumazet
> >([EMAIL PROTECTED]) wrote:
> >>>Why anyone do not want to use trie - for socket-like loads it has
> >>>exactly constant sear
"Michael K. Edwards" <[EMAIL PROTECTED]> writes:
> A better data structure for RCU, even with a fixed key space, is
> probably a splay tree. Much less vulnerable to cache eviction DDoS
> than a hash, because the hot connections get rotated up into non-leaf
> layers and get traversed enough to kee
Eric Dumazet <[EMAIL PROTECTED]> writes:
>
> So are you speaking of one memory cache miss per lookup ?
Actually two: if the trie'ing allows RCUing you would save
the spinlock cache line too. This would increase the
break-even budget for the trie.
> If not, you loose.
It all depends on if the h
On 2/18/07, Michael K. Edwards <[EMAIL PROTECTED]> wrote:
... Much less vulnerable to cache eviction DDoS
than a hash, because the hot connections get rotated up into non-leaf
layers and get traversed enough to keep them in the LRU set.
Let me enlarge on this a bit. I used to work for a compa
A better data structure for RCU, even with a fixed key space, is
probably a splay tree. Much less vulnerable to cache eviction DDoS
than a hash, because the hot connections get rotated up into non-leaf
layers and get traversed enough to keep them in the LRU set. But I am
not a data structures gu
Evgeniy Polyakov a e'crit :
On Sun, Feb 18, 2007 at 07:46:22PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
Why anyone do not want to use trie - for socket-like loads it has
exactly constant search/insert/delete time and scales as hell.
Because we want to be *very* fast. You cannot beat has
On Sun, Feb 18, 2007 at 07:46:22PM +0100, Eric Dumazet ([EMAIL PROTECTED])
wrote:
> >Why anyone do not want to use trie - for socket-like loads it has
> >exactly constant search/insert/delete time and scales as hell.
> >
>
> Because we want to be *very* fast. You cannot beat hash table.
>
> Say
Evgeniy Polyakov a e'crit :
On Mon, Feb 05, 2007 at 10:02:53AM -0800, [EMAIL PROTECTED] ([EMAIL PROTECTED])
wrote:
On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving
On Mon, Feb 05, 2007 at 10:02:53AM -0800, [EMAIL PROTECTED] ([EMAIL PROTECTED])
wrote:
> On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
>
> >I noticed in an LCA talk mention that apprently extensible hashing
> >with RCU access is an unsolved problem. Here's an idea for solving it.
> >
>
> Yes,
> For purposes of discussion, I've attached a "toy" implementation
> for doing dynamic resizing of a hashtable. It is useless, except
> as a proof of concept.
>
> I think this is very similar to what you are describing, no?
Er... not quite; that has a lot more overhead than what I was
thinking ab
On Sat, 4 Feb 2007 [EMAIL PROTECTED] wrote:
I noticed in an LCA talk mention that apprently extensible hashing
with RCU access is an unsolved problem. Here's an idea for solving it.
I'm assuming the table is a power of 2 in size with open chaining
for collisions. When the chains get too long,
1 - 100 of 102 matches
Mail list logo
