People, you have to see this patch. I have implemented the "two queues" idea proposed here, check the results by your self:
- Patch: http://goo.gl/mWven - Profiling: http://edsiper.linuxchile.cl/monkey_scheduler_optimization.png cheers! On Mon, Mar 26, 2012 at 12:59 PM, Davidlohr Bueso <[email protected]> wrote: > On Mon, 2012-03-26 at 09:32 -0600, Eduardo Silva wrote: >> On Mon, Mar 26, 2012 at 4:08 AM, Davidlohr Bueso <[email protected]> wrote: >> > On Mon, 2012-03-26 at 02:56 -0300, Felipe Astroza Araya wrote: >> >> Good aproach. It's like a stack (LIFO) of sched_connections BUT I'd >> >> prefer a linked list, because it's simpler. You could use just a "free >> >> list" and not two arrays (stack and queue). When a connection is closed >> >> his sched_connection is returned to the "free list" (head). >> >> >> > >> > It seems to be this is an overkill and the optimization is too small. We >> > can always maintain a global variable with the size of current capacity >> > - since in a threaded context it would require locking which might lead >> > to contention. Another alternative is to keep a bitmap instead of a new >> > free_in_queue array. So the bitmap would have a size of work_capacity >> > each time a slot is occupied, the corresponding bit is set. Bitmaps are >> > O(1) as well and the overhead is just 1 bit per setting >> >> would be possible to create a test case using bitmaps ? > > The following patch is simply a proof-of-concept, I believe that > optimizations here are pretty worthless - optimize where it matters! > Times are pretty similar to what Mahesh's patch does (I tested with > siege), except the overhead is minimal. This is to be expected, and is > why a simple linked lists works nicely with small worker_capacity > values. > > current O(n): > Transaction rate: 581.51 trans/sec > > bitmaps O(1): > Transaction rate: 607.66 trans/sec > > I have not run valgrind on it. Another issue with fast bitmaps is that > it is quite architecture dependent, not only dealing with 32 and 64bits, > but also using the bsf instruction for x86. This allows searching for a > specific bit in a word > (http://www.posix.nl/linuxassembly/nasmdochtml/nasmdoca.html). > > > That said, maybe we could eventually find a specific use for bitmaps, > who knows. > > Cheers. > Dave > > From 688947564cda4fad5c5d3da4d4257ebbcd3632e3 Mon Sep 17 00:00:00 2001 > From: Davidlohr Bueso <[email protected]> > Date: Mon, 26 Mar 2012 20:49:42 +0200 > Subject: [PATCH] proof of concept for client request insertions with O(1), > using bitmaps. > > --- > configure | 2 +- > src/include/mk_bitmap.h | 37 ++++++++++++++++++++++++++++++ > src/include/mk_scheduler.h | 3 ++ > src/mk_bitmap.c | 23 ++++++++++++++++++ > src/mk_scheduler.c | 54 +++++++++++++++++++++++++++---------------- > 5 files changed, 98 insertions(+), 21 deletions(-) > create mode 100644 src/include/mk_bitmap.h > create mode 100644 src/mk_bitmap.c > > diff --git a/configure b/configure > index 18e05b8..c2bfa17 100755 > --- a/configure > +++ b/configure > @@ -384,7 +384,7 @@ INCDIR = ./include > LDFLAGS = $LDFLAGS > DESTDIR = ../bin/monkey > LIBS = -ldl $libs > -OBJ = monkey.o mk_method.o mk_mimetype.o mk_request.o \\ > +OBJ = monkey.o mk_bitmap.o mk_method.o mk_mimetype.o mk_request.o \\ > mk_header.o mk_config.o mk_signals.o \\ > mk_user.o mk_utils.o mk_epoll.o mk_scheduler.o \\ > mk_string.o mk_memory.o mk_connection.o mk_iov.o mk_http.o \\ > diff --git a/src/include/mk_bitmap.h b/src/include/mk_bitmap.h > new file mode 100644 > index 0000000..e51fd7e > --- /dev/null > +++ b/src/include/mk_bitmap.h > @@ -0,0 +1,37 @@ > +#ifndef MK_BITMAP_H > +#define MK_BITMAP_H > + > +#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) > +#define BITS_PER_BYTE 8 > +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * > sizeof(long)) > +#define BITS_PER_LONG 64 > + > +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > + > +static inline unsigned long ffz(unsigned long word) > +{ > + asm("bsf %1,%0" > + : "=r" (word) > + : "r" (~word)); > + return word; > +} > +static inline void __set_bit(int nr, volatile unsigned long *addr) > +{ > + unsigned long mask = BIT_MASK(nr); > + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); > + > + *p |= mask; > +} > + > +static inline void __clear_bit(int nr, volatile unsigned long *addr) > +{ > + unsigned long mask = BIT_MASK(nr); > + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); > + > + *p &= ~mask; > +} > + > +unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long > size); > + > +#endif > diff --git a/src/include/mk_scheduler.h b/src/include/mk_scheduler.h > index fd2e442..fe95fd4 100644 > --- a/src/include/mk_scheduler.h > +++ b/src/include/mk_scheduler.h > @@ -25,6 +25,7 @@ > #include <arpa/inet.h> > > #include "mk_list.h" > +#include "mk_bitmap.h" > > #ifndef MK_SCHEDULER_H > #define MK_SCHEDULER_H > @@ -37,6 +38,7 @@ struct sched_connection > { > int status; > int socket; > + unsigned long pos_in_queue; > > time_t arrive_time; > }; > @@ -46,6 +48,7 @@ struct sched_list_node > { > unsigned short int active_connections; > struct sched_connection *queue; > + unsigned long free_in_queue[BITS_TO_LONGS(102)]; > > short int idx; > pthread_t tid; > diff --git a/src/mk_bitmap.c b/src/mk_bitmap.c > new file mode 100644 > index 0000000..be58313 > --- /dev/null > +++ b/src/mk_bitmap.c > @@ -0,0 +1,23 @@ > +#include "mk_bitmap.h" > + > +unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long > size) > +{ > + const unsigned long *p = addr; > + unsigned long result = 0; > + unsigned long tmp; > + > + while (size & ~(BITS_PER_LONG-1)) { > + if (~(tmp = *(p++))) > + goto found; > + result += BITS_PER_LONG; > + size -= BITS_PER_LONG; > + } > + if (!size) > + return result; > + > + tmp = (*p) | (~0UL << size); > + if (tmp == ~0UL) /* Are any bits zero? */ > + return result + size; > +found: > + return result + ffz(tmp); > +} > diff --git a/src/mk_scheduler.c b/src/mk_scheduler.c > index 11ee748..08a82a7 100644 > --- a/src/mk_scheduler.c > +++ b/src/mk_scheduler.c > @@ -112,28 +112,38 @@ int mk_sched_register_client(int remote_fd, struct > sched_list_node *sched) > { > unsigned int i, ret; > > - for (i = 0; i < config->worker_capacity; i++) { > - if (sched->queue[i].status == MK_SCHEDULER_CONN_AVAILABLE) { > - MK_TRACE("[FD %i] Add in slot %i", remote_fd, i); > - > - /* Before to continue, we need to run plugin stage 10 */ > - ret = mk_plugin_stage_run(MK_PLUGIN_STAGE_10, > - remote_fd, > - &sched->queue[i], NULL, NULL); > - > - /* Close connection, otherwise continue */ > - if (ret == MK_PLUGIN_RET_CLOSE_CONX) { > - mk_conn_close(remote_fd); > - return MK_PLUGIN_RET_CLOSE_CONX; > - } > + i = find_first_zero_bit(sched->free_in_queue, config->worker_capacity); > + if (i >= config->worker_capacity) { > + return -1; > + } > > - /* Socket and status */ > - sched->queue[i].socket = remote_fd; > - sched->queue[i].status = MK_SCHEDULER_CONN_PENDING; > - sched->queue[i].arrive_time = log_current_utime; > - return 0; > + if (sched->queue[i].status == MK_SCHEDULER_CONN_AVAILABLE) { > + sched->queue[i].pos_in_queue = i; > + MK_TRACE("[FD %i] Add in slot %i", remote_fd, i); > + > + /* Before to continue, we need to run plugin stage 10 */ > + ret = mk_plugin_stage_run(MK_PLUGIN_STAGE_10, > + remote_fd, > + &sched->queue[i], NULL, NULL); > + > + /* Close connection, otherwise continue */ > + if (ret == MK_PLUGIN_RET_CLOSE_CONX) { > + mk_conn_close(remote_fd); > + return MK_PLUGIN_RET_CLOSE_CONX; > } > + > + /* Socket and status */ > + sched->queue[i].socket = remote_fd; > + sched->queue[i].status = MK_SCHEDULER_CONN_PENDING; > + sched->queue[i].arrive_time = log_current_utime; > + __set_bit(i, sched->free_in_queue); > + return 0; > } > + else { > + /*This should never happen*/ > + mk_err("worker : invalid free position in queue found"); > + } > + > > return -1; > } > @@ -229,10 +239,13 @@ int mk_sched_register_thread(int efd) > __sync_bool_compare_and_swap(&sl->epoll_fd, sl->epoll_fd, efd); > sl->queue = mk_mem_malloc_z(sizeof(struct sched_connection) * > config->worker_capacity); > + > sl->request_handler = NULL; > > for (i = 0; i < config->worker_capacity; i++) { > sl->queue[i].status = MK_SCHEDULER_CONN_AVAILABLE; > + __clear_bit(i, sl->free_in_queue); > + sl->queue[i].pos_in_queue = i; > } > return sl->idx; > } > @@ -328,6 +341,7 @@ int mk_sched_remove_client(struct sched_list_node *sched, > int remote_fd) > __sync_fetch_and_sub(&sched->active_connections, 1); > sc->status = MK_SCHEDULER_CONN_AVAILABLE; > sc->socket = -1; > + __clear_bit(sc->pos_in_queue, sched->free_in_queue); > return 0; > } > else { > -- > 1.7.4.1 > > > -- Eduardo Silva http://edsiper.linuxchile.cl http://www.monkey-project.com _______________________________________________ Monkey mailing list [email protected] http://lists.monkey-project.com/listinfo/monkey
