From: Campbell Boucher-B. <Cam...@sa...> - 2002-04-23 21:18:36
|
All true, and brain starting to hurt again as I make my way through yet another support library (concurrency) and new code :-) No reflection on the writer(s). Just lots of code to digest during a 1 hour speed read (unfinished). From a really quick look, I'd say you've just reached square one (a working...prototype). Based on this and your comments in-line in the code, I'd say that the 10x figure will drop significantly as it is worked out (slowly or not) how to make the implementation more efficient and less dependent on (a very nice, and very convenient, but) generalized library code. Perhaps I'm wrong in this evaluation, but we all know how [easy|hard] it is at times to realize an order of magnitude (or at least close) speedup/slowdown when moving from an idea, to a prototype, to final, optimized code. I personally wouldn't worry too much about this intitial result, unless you have already profiled and analyzed the hell out it and been unable to come up with any clues that perhaps the generalization is less efficient than it could be or "safer" than it has to be. I read the concurrency library docs quickly, and the impression I got was that fair to average but consistent across JVM and strictly correct behaviour were the overall goals, while several sections repeated that there were definitely more efficient/faster implementaions to be had for specific use-cases. OTOH, if you really think that a simpler algorithm and coarser locking are the guaranteed way to go, by all means go with that (like I'm in any position or have any desire to dictate things). Once again, I'm just happy that something has come of our earlier discussions on the matter (a contrapositive is just as good a positive when working out initial directions and avoiding long commitments to dead-ends and roads of heartache), and I think its great that you had the motivation to get as far as you have so quickly. The nice thing about getting to square one is that refinement can be done slowly but surely, without having to get all uptight about having something that at least works and exhibits certain desirable characteristics that one set out to capture. The really nice thing about having *any* concurrent indexing scheme in place is that at some point (with enough CPUs) it will pay off in terms of scalability. I know that single processor systems seem to keep following the exponential clock speed curve, but I also notice that quad and 8-way pIII 550 Intel Xeon servers seem to pop up regularly on e-bay for between $1500 and $6000 USD, complete with 4x9 or 2x18 10,000 RPM SCSCI or better and 1GB or better. I can't help but imagine that in the next few years it will be impossible to make money as a PC manufacturer/vendor without selling several CPUs per unit. That is, I think that SMP machines will probably make it onto the desktop or at least into every small business one of these days. Of course, I may be a fool for thinking that. Just look how well dedicated shared memory/shared disk/custom CPU SMP special-purpose database machines have faired over the last decade. At one point, that was going to be "the bright future" of database system development (not that everyone bought the story). However, all the major (server-oriented) OSes seem now to have support for SMP, while SMP boards and CPUs just keep getting cheaper, so I expect that at least 2-way machines should become rather more common than they are now. And just how many more times can clock speed be doubled? How much more speculative execution will return a bang for the buck? How wide can VLIW go before returns diminish? To me, the whole idea of introducing B-link concurrent indexing hinges on two (well maybe three) things: 1.) Do we want/expect hsqldb to be used under a mix of long and short transactions, and if so, do we want it to exhibit "nice" or "fair" behaviour, providing good percieved throughput at the expense of absolute transaction processing speed? 2.) Do we want/expect hsqldb (or at least some targeted build) to be used regularly in SMP scenarios? 3.) At what expense are we willing to buy points 1.) & 2.), given that we decide that we really, really want them. Campbell ----- Original Message ----- From: "Karl Meissner" <mei...@ya...> To: "Campbell Boucher-Burnet" <Cam...@sa...>; <hsq...@li...> Sent: Tuesday, April 23, 2002 11:10 AM Subject: Re: [Hsqldb-developers] Re: fine grain threading > > Fine grain locking may be 10x slower than with no > > locking, but as I recall from our mutual reading and > > discussions w.r.t. B-link trees, updaters only block > > each other (not readers) > > The way I had to code it, readers still need to do a > synchronized check if they are blocked by a writer. > The readers pay the 10X cost just for checking. That > is not counting being blocked. > > It there is a way for the readers to not do a check it > would go faster. Any suggestions would be very > interesting. > > > and only on competing for > > individual node locks, unlike some tree > > That is basically why the cost higher. The check is > per node so an read requires about 4 checks (best case > (actaully 7 if we are using the cache)) vs a course > grain lock would only require 1 check > > It is the read_lock_aquire() that is sucking up all > the time . > > > implementations that require require whole path > > locks to do updates (i.e. B-link trees are highly > > localized w.r.t. rebalancing, as opposed to > > pessimistic locking under T-Trees which tends to > > lock the entire path from the root to the node being > > updated). As such the overall number of locks is > > still lower than for many other approaches, and > > That is why I am currently leaning toward coarse > locking. It is the least amount of locking. > > > using the lateral traverse link pointer, readers > > sail through, guaranteed that they will always > > eventually find the correct leaf node (if it exists) > > yes it is in the code I implemented. > > > or properly fail the search. > > > > So I would suspect that until a very high % of > > activity becomes both read and update activity > > against a particular index in a particular table, > > this 10x overhead will really represent a much > > smaller overhead in terms of the overall time to > > possibly true. > If a index lookup is only 1% of the time spend dealing > with the query, then inflating it by 10 to get > finegrain locking may be ok. > Depends on the relative costs in the rest of the > system. > > > process any particular statement. OTOH, what this > > does buy is virtually unblocked multiple concurent > > readers under multiple concurent writers, allowing a > > mix of short and long running queries to experience > > better perceived throughput; I think this will be > > yes. fine grain locking is 'fairer' to multiple > threads. If a very long query starts and then a short > read starts, the short read will not be greatly held > up by the long query. > But that price seems to be all index operation go 10X > slower. > > >And when > > developing software for the typical end-user, it is > > alway good to be able to provide a perceived > > increased responsiveness that is, within reason, > > closer to what the end-user expects than was > > previously being delivered. > > It would be possible to make it configurable. Maybe > turn on and off fine grain checks. That would give a > developer a choice. On the other hand BLinks are > much more complicated to code. I still don't have a > good delete function > > > > > On another line of thought, straight BTrees may end > > up being even slower than B-link under concurrent > > access, > > I will let you know, I should have a BTree varient > sometime next week. > > > using the same level of granularity (just a > > thought...since you've already implmented B-link. > > OTOH, maybe not). Have you done the research or > > analysis yourself to determine this one way or > > another? > > > > Responding to another point, perhaps some middle > > ground can be found for granularity that lies > > > One idea I had was that updates completely lock the > table but all reads were unsynchronized. This gives > you single check of course grain, but at least allows > lots of reads to occure. > > > > between locking single nodes and locking entire > > high-level structures? Certainly, there are > > opportunities, for example, to lazily rebalance, > > BTrees would not change depth in a rebalance but they > would be able to release deleted memory. > > > concurrent vs thread-safe multiplexed) operation can > > be switched, based on load. That is, with a single > > yes but complicated. Dont forget now you have added > another synchronized check to what the current mode is > > > > > ===== > Karl Meissner > > ........................................................... > : Meissner Software Development, LLC : > : "Software development and project management services." : > : http://meissner.v0.net/resume.htm : > ........................................................... > > __________________________________________________ > Do You Yahoo!? > Yahoo! Games - play chess, backgammon, pool and more > http://games.yahoo.com/ |