Re: Best Way To Lookup From a Huge Table

FROM : John Stiles
DATE : Fri Mar 21 21:51:33 2008

Michael Ash wrote:
> On Fri, Mar 21, 2008 at 12:13 PM, John Stiles <<email_removed>> wrote:
> 

>>  Michael Ash wrote:
>>  For what it's worth, I wrote a quick test program creating 50,000
>> random key/value pairs of NSStrings of around 500 characters each,
>> then inserted them into an NSDictionary. My quick code compiled with
>> no optimizations took 200 milliseconds to insert all 50,000 strings
>> into an NSMutableDictionary. This is admittedly on a much faster
>> machine (a 2.66GHz Mac Pro) and your objects may have been
>> substantially more complex to hash or compare, but the above does not
>> build a convincing case for the STL option in my mind.
>>  You're only comparing apples and oranges if you don't port your test code
>> to STL and test it yourself.
>>  There's simply no such thing as a fair comparison between a G4 running on
>> battery power and an Intel Xeon.
>>   

>
> I never claimed otherwise. I simply find it odd when people act as
> though good performance on tens of thousands of records were somehow
> exceptional or difficult. It was such once upon a time, but with
> modern CPUs and good data structures easily available in libraries, it
> really isn't anymore.
>
> But just for fun, I implemented a std::map version of my test as well.
> Both versions take somewhat under 200ms, with the differences between
> them completely overwhelmed by per-run variances.
>
> The lesson here, as usual, is to Optimize Later. Use what produces the
> best code and what you're most comfortable with. For me that means
> staying far, far away from the STL. For others it may mean using
> ObjC++ and the STL over Cocoa collection classes. But choosing one
> over the other for speed when you don't have working code yet is
> putting the cart before the horse.

It's fine that you are uncomfortable with STL, but there's nothing about
your results that makes me think "this doesn't build a convincing case
for the STL option." If its performance is on par, then it's a highly
convincing case. std::map actually does more than NSDictionary—it sorts
its entries instead of keeping them in random order. Also, it copies its
keys instead of just keeping a reference to them, which is also more
work—it would be a much fairer test if you used std::string* pointers
for your keys and values instead of std::string objects, but it'd also
be a little more work since you'd need a custom comparator and you'd
need to consider memory management (which boost smart pointers
apparently can manage pretty well).

YMMV, but I like the capabilities of the STL and I think it's a pretty
powerful tool to have in one's toolbox. Not that I think you should be
forced to use it—feel free to use Foundation classes if you like them
better—but don't let bias stand in the way of reasonable comparisons.