On Fri, Feb 6, 2009 at 5:46 PM, Monty Taylor <[email protected]> wrote:
> Padraig wrote: > > Blueprint changed by Padraig: > > > > Whiteboard changed to: > > First of all, great write up. I would love it if you'd take this text > and make a page on the drizzle.org wiki with it, and then fill in the > Wiki-page for the specification on the blueprint. Done. I added a Blueprints section to the Developer/Contributor documentation page (http://drizzle.org/wiki/Developer_Documentation). The actual wiki page with the text I wrote up is at: http://drizzle.org/wiki/Replace_QUEUE > > > > We have started this effort off by replacing the use of QUEUE in > > mysys/thr_alarm.cc. The code in this file is only executed when a KILL is > used > > on a session thread which Jay mentioned does not occur very often on the > > mailing list. > > > > In mysys/thr_alarm.cc, we have a queue which consists of elements of type > ALARM entitled > > alarm_queue: > > > > static QUEUE alarm_queue; > > > > The queue may contain multiple ALARMs with the same thread id. > alarm_queue > > sorts via expire_time, but must clean out the queue of other ALARMs with > the > > thread_id that has been killed, which means that an iterator must be used > to > > traverse the queue. > > > > Based on discussions on the mailing list, std::vector was chosen to > replace > > QUEUE since it's a standard, simple solution. Thus, we are replacing the > above with: > > > > static std::vector<ALARM*> alarm_stack; > > > > An issue which Monty mentioned on the mailing list was that you cannot > > remove elements from a vector while iterating through an active iterator. > > There are 2 occasions in mysys/thr_alarm.cc where some logic like this is > > needed. Thus, we defined 2 function objects which can be used for this > > purpose. I defined these function objects at the top of the file, since I > > wasn't sure where else I should put them. Should I put them in a header > > file? Or should they be in the function that they are called from? > Anyway, > > these function objects are: > > Since these implementation details, I'd just leave them in thr_alarm.cc. > If they could be generalized or used in other places, then it would be > worthwhile putting them in their own header. > > It would certainly not _hurt_ to make a header for each one... but I > think having them in thr_alarm.cc is fine. > > > class alarm_if > > { > > public: > > inline bool operator()(ALARM *current_alarm) > > { > > current_alarm->alarmed= 1; /* Info to thread */ > > if (pthread_equal(current_alarm->thread,alarm_thread) || > > pthread_kill(current_alarm->thread,thr_client_alarm)) > > { > > return true; > > } > > return false; > > } > > }; > > > > class alarm_if_time > > { > > time_t alarm_time; > > time_t alarm_time_next; > > public: > > alarm_if_time(time_t now, time_t next) : alarm_time(now), > > alarm_time_next(next) { } > > inline bool operator()(ALARM *current_alarm) > > { > > if (current_alarm->expire_time <= alarm_time) > > { > > current_alarm->alarmed= 1; /* Info to thread */ > > if (pthread_equal(current_alarm->thread,alarm_thread) || > > pthread_kill(current_alarm->thread,thr_client_alarm)) > > { > > return true; > > } > > else > > { > > current_alarm->expire_time= alarm_time_next; > > } > > } > > return false; > > } > > }; > > > > We will discuss where these function objects are used later. Every > occurence > > of alarm_queue.elements in the code is replaced with alarm_stack.size(). > > Good. > > > The first modification we made was to the init_thr_alarm() function. In > this function, > > instead of: > > > > init_queue(&alarm_queue,max_alarms+1,offsetof(ALARM,expire_time),0, > > compare_uint32_t,NULL); > > > > We now have: > > > > alarm_stack.reserve(max_alarms+1); > > Great. > > > Next, in the function resize_thr_alarm(), we will replace the following: > > > > if (alarm_queue.elements < max_alarms) > > resize_queue(&alarm_queue,max_alarms+1); > > > > With this: > > > > if (alarm_stack.capacity() < max_alarms) > > alarm_stack.resize(max_alarms+1); > > Great. > > > Next, in the thr_alarm function, we replace queue insertion, which is: > > > > queue_insert(&alarm_queue,(unsigned char*) alarm_data); > > > > with the following (not too sure if I should just change this to > > alarm_stack.push_back(alarm_data)): > > > > std::vector<ALARM*>::iterator p= alarm_stack.begin(); > > /* No need to coerce to uchar* since std::vector<> is templatized */ > > alarm_stack.insert(p, alarm_data); > > I think push_back would be fine, unless this would keep something in an > incorrect order. If you do need to keep the above semantics, I think it > would also be fine to do: > > alarm_stack.insert(alarm_stack.begin(), alarm_data); > > since that iterator doesn't actually have any purpose in life other than > that statement. Good point. I'm going to keep the original semantics for the moment but I adjusted my code thanks to your feedback. > > > > The next modification needed occurs in the thr_end_alarm() function. > > Originally, the code was: > > > > alarm_data= (ALARM*) ((unsigned char*) *alarmed - > offsetof(ALARM,alarmed)); > > for (i=0 ; i < alarm_queue.elements ; i++) > > { > > if ((ALARM*) queue_element(&alarm_queue,i) == alarm_data) > > { > > queue_remove(&alarm_queue,i); > > if (alarm_data->malloced) > > free((unsigned char*) alarm_data); > > found++; > > break; > > } > > } > > > > This has been modified to the following: > > > > alarm_data= (ALARM*) ((unsigned char*) *alarmed - > offsetof(ALARM,alarmed)); > > For your next project... figuring out if there's a way to avoid that ^^ > would be wonderful. I get what it's there, but egads. :) > > > std::vector<ALARM*>::iterator p= alarm_stack.begin(); > > while (p != alarm_stack.end() && *p != alarm_data) > > p++; > > if (p != alarm_stack.end()) > > These are fine, although they sort of feel like they could be replaced > with a find_if: > > std::vector<ALARM*>::iterator p= > find_if(alarm_stack.begin(), > alarm_stack.end(), > bind2nd(equal<ALARM *>(), alarm_data)); > if (p !- alarm_stack.end()) > > > { > > /* p now points to the current alarm pointer; remove it */ > > if (alarm_data->malloced) > > free(*p); > > alarm_stack.erase(p); > > found= 1; > > } > > > Next, come the use of the function objects we defined earlier. These > > modifications are not as straightforward and would appreciate any > feedback > > on these. The 2 modifications are in the process_alarm_part2() function. > The > > first was to modify the following code: > > > > uint32_t i; > > for (i=0 ; i < alarm_queue.elements ;) > > { > > alarm_data=(ALARM*) queue_element(&alarm_queue,i); > > alarm_data->alarmed=1; /* Info to thread */ > > if (pthread_equal(alarm_data->thread,alarm_thread) || > > pthread_kill(alarm_data->thread, thr_client_alarm)) > > { > > queue_remove(&alarm_queue,i); /* No thread. Remove alarm */ > > } > > else > > i++; /* Signal next thread */ > > } > > > > This is modified to use the function object alarm_if and now looks as > > follows: > > > > alarm_stack.erase(remove_if(alarm_stack.begin(),alarm_stack.end(), > > alarm_if()),alarm_stack.end()); > > > > The above code essentially goes through the entire alarm_stack vector and > removes an > > element from the vector if the function object returns true. Monty > suggested > > an approach like this on the mailing list as it is safer than removing > > elements from a vector while iterating through an active iterator. > > Yes. the v.erase(remove_if(v.begin(), v.end(), predicate()), v.end) is a > common patter. > > > The second modification in process_alarm_part2() is to modify the > following > > code: > > Heh. process_alarm_part2(). What a wonderful function name. ;) > > > while ((alarm_data= (ALARM*) queue_top(&alarm_queue))->expire_time <= > now) > > { > > alarm_data->alarmed=1; /* Info to thread */ > > if (pthread_equal(alarm_data->thread,alarm_thread) || > > pthread_kill(alarm_data->thread, thr_client_alarm)) > > { > > queue_remove(&alarm_queue,0); /* No thread. Remove alarm */ > > if (!alarm_queue.elements) > > break; > > } > > else > > { > > alarm_data->expire_time=next; > > queue_replaced(&alarm_queue); > > } > > } > > #ifndef USE_ALARM_THREAD > > if (alarm_queue.elements) > > { > > alarm((uint32_t) (alarm_data->expire_time-now)); > > next_alarm_expire_time= alarm_data->expire_time; > > } > > #endif > > > > The issue I have with replacing the above code is that I can use the > > alarm_if_time function object to iterator through the elements in the > > alarm_stack vector and remove any elements as appropriate based on the > same > > condition as in the original code. The problem I have is with the > following > > code block: > > > > #ifndef USE_ALARM_THREAD > > if (alarm_queue.elements) > > { > > alarm((uint32_t) (alarm_data->expire_time-now)); > > next_alarm_expire_time= alarm_data->expire_time; > > } > > #endif > > > > I don't know how I can keep track of what the last ALARM that was > processed > > is. Although, I'm thinking it will be the ALARM with the smallest > > expire_time as that will be the ALARM that is at the top of the > alarm_queue > > in the current implementation if I am correct? The reason I think this is > > because at the start of the while loop in the original code, the ALARM > from > > the top of alarm_queue is always used. Thus, at the moment, I am > replacing > > the above code with: > > > > alarm_stack.erase(remove_if(alarm_stack.begin(),alarm_stack.end(), > > alarm_if_time(now, next)),alarm_stack.end()); > > Ah ... here we see why there were using a queue before. Your approach > below of finding the lowest expire_time seems fine. Cool. Thanks for the confirmation. I really wanted someone with more familiarity with this code to have a look at it. > > > > #ifndef USE_ALARM_THREAD > > if (alarm_stack.size()) > > { > > std::vector<ALARM*>::iterator p= alarm_stack.begin(); > > ALARM *smallest_expire_time; > > while (p != alarm_stack.end()) > > { > > ALARM *current_alarm= *p; > > if (!smallest_expire_time) > > { > > smallest_expire_time= current_alarm; > > } > > else > > { > > if (current_alarm->expire_time < smallest_expire_time->expire_time) > > smallest_expire_time= current_alarm; > > } > > p++; > > } > > if (smallest_expire_time) > > { > > alarm((uint32_t) (smallest_expire_time->expire_time-now)); > > next_alarm_expire_time= smallest_expire_time->expire_time; > > } > > } > > #endif > > > > The next modifications are in the thr_alarm_kill() function. The > following > > code is modified: > > > > for (i=0 ; i < alarm_queue.elements ; i++) > > { > > if (((ALARM*) queue_element(&alarm_queue,i))->thread_id == thread_id) > > { > > ALARM *tmp=(ALARM*) queue_remove(&alarm_queue,i); > > tmp->expire_time=0; > > queue_insert(&alarm_queue,(unsigned char*) tmp); > > reschedule_alarms(); > > break; > > } > > } > > > > This is tricky because we are removing an element from alarm_queue, > > modifying it, and then placing the element back in alarm_queue again. I'm > > not sure if I'm doing this in the best way but here is what I changed > this > > code to: > > > > std::vector<ALARM*>::iterator p= alarm_stack.begin(); > > while (p != alarm_stack.end()) > > { > > ALARM *current_alarm= *p; > > if (current_alarm->thread_id == thread_id) > > break; > > p++; > > } > > > > if (p != alarm_stack.end()) > > { > > ALARM *tmp= *p; > > alarm_stack.erase(p); > > tmp->expire_time= 0; > > alarm_stack.insert(p,tmp); > > reschedule_alarms(); > > } > > > > Again, maybe it would be better to just use alarm_stack.push_back(tmp) > above > > instead of using the insert() method. Any suggestions here? > > Well, again it depends on how important the order is. I'm guessing it's > not since we just about always iterate through the queue. If it's not, > then I think push_back is likely to be less work than insert - but I > don't have proof of that. > > But why erase it and re-insert it? Couldn't you just do : > (*p)->expire_time= 0; > reschedule_alarms(); > ? The more I read the original code, the more I think the remove/insert > was just an artifact of how QUEUE was written. Ah ok. That code was really confusing to me alright. I pretty much just tried to preserve the original semantics. I've modified it to what you suggested though. Again, thanks for the feedback there. > > > > Those are all the major modifications that were needed to replace the use > of > > QUEUE in mysys/thr_alarm.cc > > > > I have compiled this, and just run make test and all tests succeed after > > making modifications. I was wondering if anyone knew of a way I could > test > > this piece of code specifically? Also, do we want to try and benchmark > > performance before and after the removal of QUEUE? > > Yeah. That's the tricky part. Anybody else got a good testing > suggestion? Jay? I'm working right now on a continuous benchmarking > thing so we can check for performance regressions, but it's not quite > done yet. > > > I pushed this code to the branch which is linked to this blueprint: > > > > lp:~posulliv/drizzle/code-cleanup-c++-replace-queue > > Great. Submit a merge proposal when you're happy with testing of it and > it's ready for a merge and I'll grab it. Done. Ive just done standard testing of it and I have not run in to any problems with it. I'm open to any suggestions for testing from anyone though? -Padraig > > > Monty >
_______________________________________________ Mailing list: https://launchpad.net/~drizzle-discuss Post to : [email protected] Unsubscribe : https://launchpad.net/~drizzle-discuss More help : https://help.launchpad.net/ListHelp
