On Wed, Jun 05, 2013 at 14:13, Alexandre Ratchov wrote:
> On Tue, Jun 04, 2013 at 11:33:12PM -0400, Ted Unangst wrote:
>> Instead of using a fixed size hash table for procs, use an rb tree.
>>
>> Makes thread/process lookup even more web scale.
>>
>
> any measurement?
o ye of little faith...
stock
54.65
57.29
54.54
rbproc
47.27
47.34
47.16
Benchmark code is below. Now you may well complain that I cooked the
test to give me the result I want. If you remove the pid colliding
code pertaining to 42, the results are different.
stock
37.16
37.52
37.07
rbproc
47.20
46.84
46.51
Perhaps a more realistic test is called for, like building a kernel.
stock
1m24.51s real 4m6.24s user 0m43.34s system
1m24.12s real 4m7.64s user 0m41.98s system
rbproc
1m24.02s real 4m6.90s user 0m43.65s system
1m23.88s real 4m6.07s user 0m41.73s system
rbproc wins by a hair, but I am happy to call it a draw.
Conclusion? You'll never notice the difference. Personally I have a
slight preference for improving worst case behavior. The hash table
isn't *that* large today, but as we increase maxthreads it will get
bigger. I prefer dynamic structures to statically sized structures.
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
static __inline uint64_t
rdtsc(void)
{
uint32_t hi, lo;
__asm __volatile("rdtsc" : "=d" (hi), "=a" (lo));
return (((uint64_t)hi << 32) | (uint64_t) lo);
}
const int loops = 2560000;
const int maxproc = 50;
int
main()
{
int pidhash = 511;
int nprocs;
int pids[200];
int i, p, pid;
uint64_t before, after;
printf("creating pids\n");
nprocs = 0;
while (nprocs < maxproc) {
pid = fork();
switch (pid) {
case 0:
if ((getpid() & pidhash) != 42)
_exit(0);
while (1)
sleep(1);
break;
case -1:
for (p = 0; p < nprocs; p++)
kill(pids[p], 9);
printf("failed after %d %d\n", nprocs, errno);
exit(1);
default:
if ((pid & pidhash) == 42)
pids[nprocs++] = pid;
else
waitpid(pid, NULL, 0);
}
}
printf("benchmarking...\n");
before = rdtsc();
for (i = 0; i < loops; i++)
for (p = 0; p < nprocs; p++)
kill(pids[p], 0);
after = rdtsc();
for (p = 0; p < nprocs; p++)
kill(pids[p], 9);
printf("%.2f\n", (after - before) / 1000000000.0);
}
