Phil:
Thanks for the complement.
Wow, this is the first (that I remember) verification of somebody
reading the the application notes on Judy. I had forgotten all about
them. They were designed to be innovative and interesting -- or at
least I thought. I have never been asked a question about any of
them.
<http://judy.sourceforge.net/examples/count_by_value.pdf >
That application note you call "striped" is the simplest and unintuitive
one. I believe it was written by Bob Montgomery, or at least suggested
by him. I don't remember why his name is not on the paper.
At the time, I could not think of a use for that algorithm, but it seems
you have found one. I would like to understand more of the details.
If you need confidentiality, email me privately.
I see your data seems to compare two methods -- JudyL(native) and
Judy1(striped). The striped version is unbelievable fast (addition) if
the sums cover a lot of numbers. I have used the analogy of "faster
than the speed of light" I.E. addition (+) done faster than light could
travel across the CPU chip. Of course the "real" partial additions were
done at the time of insertion. I assume that your data sets do not have
a lot of numbers (Values) to sum, since you are comparing with JudyL.
I am still working on Judy and could spend time of improving areas such
as the "counting" speed. That has always been on my list, but at a low
priority. I have had very little feedback on people using that feature
of Judy.
Thanks for your interest,
Doug Baskins
Doug Baskins <[email protected]>
>________________________________
> From: Phil Stanhope <[email protected]>
>To: [email protected]
>Cc: [email protected]
>Sent: Thursday, March 29, 2012 5:45 AM
>Subject: Re: I'd like to congratulate you and the team that worked on Judy
>Arrays
>
>
>See below. When I say "striped" I'm referring specifically to this:
>http://judy.sourceforge.net/examples/count_by_value.pdf
>
>Naive is a staight JUDYL implementation.
>
>I'm using network address ranges (a subset of a potential of 4GB IPV4
>addresses). The range is not random across the 4GB space. But nonetheless it's
>"sparse" in terms of total potential # of keys.
>
>More below.
>
>
>
>On Thu, Mar 29, 2012 at 5:58 AM, Alan Silverstein <[email protected]> wrote:
>
>Phil,
>>
>>
>>> My point about doing things in software in the cloud is that the
>>> reason for this initial work is to build what amounts to a real-time
>>> IP filter/throttle. That's stuff that's been solved for years.
>>
>>Do you mean, using dedicated HW?
>>
>>
>>
>
>Exactly.
>
>
>> But in a cloud hosting environment -- you don't get to put a h/w
>>> device in front of your infrastructure of rented machines that you
>>> spin up/down on demand. Sure, the hoster may have that type of
>>> infrastructure -- but you as the lessee don't get access to it.
>>
>>Let me see if I follow you... Cloud computing, for example, is using
>>modern computing speed to virtualize features that were formerly in HW.
>>Somewhat ironically, problems previously solved in dedicated HW are now
>>re-instantiated in SW too. Is that it?
>>
>>
>>
>
>Exactly.
>
>
>> In my physical data centers -- I can rely on physical devices for this
>>> type of work. But in my cloud data centers -- I need to incorporate
>>> this as a last line of defense against overloading some of my service
>>> endpoints. This is but one use case.
>>
>>OK.
>>
>>
>>> Note -- I've done no tuning whatsoever. Just built libjudy (on either
>>> OSX 64-bit or CentOS 6.2 64-bit). Worked unchanged as you'd
>>> hope/expect.
>>> CPU caches are bigger than they used to be. And there are two-levels
>>> of cache. I wonder if this could be tweaked to improve performance
>>> even more.
>>
>>I suppose so!
>>
>>
>>> Since you raise IPV6 -- it's 128-bit ... so it would take two striped
>>> Judy1 arrays (well 64 Judy1 I guess) to have a IPV6 sparse array.
>>
>>What do you mean by striped in this context? I think in terms of
>>array-of-array where each level decodes a byte (within libJudy code) or
>>a word (32/64) at the client level. On a 64-bit system (which pretty
>>much everything is these days, 32 is consider a microprocessor), JudyL
>>array of JudyL array should suffice, just two levels.
>>
>>
>>
>
>Striped array as used in this =>
>http://judy.sourceforge.net/examples/count_by_value.pdf
>
>> We don't accept IPV6 for our service yet. I'll hold off on that
>>> implementation for now. But I do want to create a simple library for
>>> tracking in real-time a set of stats per key (count, min/max, etc).
>>> It'd be pretty simple to pack these types of counters into a small
>>> collection of these arrays. Track 4-5 key metrics on working expanse
>>> of 256MB keys in < 64MB of memory. Yeah -- I remember when that was
>>> an extraordinary amount of memory. But these days -- tiny fragment (I
>>> just ordered a under-desktop test server today with 64GB of memory).
>>
>>Yup. About 33 years ago in very nearly this same spot (I'm back in
>>Building 1 at the HP/Avago Fort Collins site), we wrote business
>>software (like accounts receivable and order entry) for a computer with
>>32K BYTES of main memory.
>>
>>
>>
>
>My first paying job as a programmer was to write an inventory control system
>on an HP-250 in late 1981. http://www.hpmuseum.net/display_item.php?hw=249
>
>:)
>
>
>> Here's the updated test stats -- think I got my timing counters right
>>> this time. The last one had an incorrect printf -- showed count &
>>> init time value. Added cost to iterate through every Index value as
>>> well as calcuate average retrieval. Nothing is random at this point.
>>> But don't expect much if any change given what's going on under the
>>> covers.
>>
>>Groan, a data dump. :-) OK, what does this mean?
>>
>>
>>> ~/Downloads/ystud (master)> ./counter_test 1.0.0/4
>>> CIDR 1.0.0/4 has 0x10000000 (268435456) addrs netmask=F0000000 from
>>> 00000000 (0.0.0.0) to FFFFFF0F (15.255.255.255)
>>
>>This is the range, not the current population, right?
>>
>>
>>
>
>The range became the population. I'll be updating. But I took a separate
>program that was validating some network range calculations & masking
>capabilities and added the judy stuff to it.
>
>
>> JUDY1 (striped) keys=268435456 size=0016.07MB init=26.909740s
>>> count=0.000006s get=0.119964us iter=32.202682s
>>> JUDYL (naive) keys=268435456 size=2128.07MB init=42.306259s
>>> count=0.001110s get=0.119445us iter=32.063248s
>>
>>Not sure what striped and naive mean here. Are the key counts real
>>(actually loaded) or potential? Anyway yeah, small and fast is the name
>>of the game...
>>
>>
>
>Actually loaded.
>
>
>And have started to use this in a different way ... but been stalled this week
>now that I'm back from Beijing and dealing with other stuff.
>
>The modern equivalent -- sort of -- is something called LevelDB from Google.
>http://code.google.com/p/leveldb/
>
>
>Anyway, in real life in recent projects I've actually created some
>>fairly elaborate libJudy structures and had them work well, like JudyL
>>=> JudyL => Judy1, and inverse lookups (map and back-map).
>>
>>Cheers,
>>Alan
>>
>
>
>
------------------------------------------------------------------------------
This SF email is sponsosred by:
Try Windows Azure free for 90 days Click Here
http://p.sf.net/sfu/sfd2d-msazure
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
