61040aa5fe6c3f3e6b836570cc265750ecba7e3a
[ccan] / ccan / antithread / examples / arabella.c
1 /* Antithread example to approximate picture with triangles using
2  * genetic algorithm.   Example for a 2 cpu system:
3  *      ./arabella arabella.jpg out out.save 2
4  */
5 #include <stdio.h>
6 #include <jpeglib.h>
7 #include <ccan/talloc/talloc.h>
8 #include <err.h>
9 #include <assert.h>
10 #include <limits.h>
11 #include <string.h>
12 #include <stdint.h>
13 #include <math.h>
14 #include <sys/select.h>
15 #include <ccan/str/str.h>
16 #include <ccan/antithread/antithread.h>
17 #include <sys/types.h>
18 #include <unistd.h>
19
20 // Define this to run 100 times without dumping state
21 //#define BENCHMARK
22
23 /* How many drawings in entire population. */
24 #define POPULATION_SIZE 1000
25
26 /* How many generations without 1% improvement before we terminate. */
27 #define PLATEAU_GENS 200
28
29 /* An image buffer to render into. */
30 struct image {
31         unsigned height, width;
32         unsigned int stride;
33         /* RGB data */
34         unsigned char *buffer;
35 };
36
37 /* A drawing is a (fixed) number of triangles. */
38 struct drawing {
39         struct triangle *tri;
40         unsigned int num_tris;
41         unsigned long score;
42 };
43
44 /* Here's a triangle. */
45 struct triangle {
46         struct {
47                 unsigned int x, y;
48         } coord[3];
49
50         /* RGBA */
51         unsigned char color[4];
52         unsigned char mult;
53         uint16_t add[3];
54 };
55
56 /* Get pointer into image at a specific location. */
57 static unsigned char *image_at(struct image *image,
58                                unsigned int x, unsigned int y)
59 {
60         return image->buffer + y * image->stride + x * 3;
61 }
62
63 /* Blend a dot into this location. */
64 static void add_dot(unsigned char *buf,
65                     unsigned char mult, const uint16_t add[])
66 {
67         unsigned int c;
68         /* /256 isn't quite right, but it's much faster than /255 */
69         for (c = 0; c < 3; c++)
70                 buf[c] = (buf[c] * mult + add[c]) / 256;
71 }
72
73 /* Code based on example taken from:
74  * http://www.devmaster.net/forums/showthread.php?t=1094 */
75 static void add_flat_triangle(struct image *image,
76                               int x0, int y0, int x1, int y1, int x2, int y2,
77                               unsigned char mult, const uint16_t add[])
78 {
79         unsigned char *buf;
80         unsigned int i, j;
81
82         // compute slopes for the two triangle legs
83         float dx0 = (float)(x2 - x0) / (y2 - y0);
84         float dx1 = (float)(x2 - x1) / (y2 - y1);
85         
86         int yRange = 0;
87         
88         float lx = (float) x0, rx = (float) x1;
89         
90         if (y0 < y2) { 
91                 yRange = y2 - y0;
92                 buf = image_at(image, 0, y0);
93         } else {
94                 yRange = y0 - y2;
95                 buf = image_at(image, 0, y2);
96                 lx = rx = (float)x2;
97         }
98
99         for (i=0; i < yRange; ++i) {
100                 for (j=(int)(lx); j<(int)((rx) + 1.0f); ++j)
101                         add_dot(buf + 3 * j, mult, add);
102         
103                 lx  += dx0;
104                 rx  += dx1;
105                 buf += image->stride;
106         }
107 }
108
109 static void swap(int *a, int *b)
110 {
111         int tmp = *a;
112         *a = *b;
113         *b = tmp;
114 }
115
116 static void paint_triangle(struct image *image, const struct triangle *tri)
117 {
118         int i0 = 0, i1 = 1, i2 = 2;
119         int x0, y0, x1, y1, x2, y2;
120
121         /* Could do this on triangle creation. */
122         // sort verts by height
123         if (tri->coord[i0].y > tri->coord[i1].y) swap(&i0, &i1);
124         if (tri->coord[i0].y > tri->coord[i2].y) swap(&i0, &i2);
125         if (tri->coord[i1].y > tri->coord[i2].y) swap(&i1, &i2);
126
127         x0 = tri->coord[i0].x, y0 = tri->coord[i0].y;
128         x1 = tri->coord[i1].x, y1 = tri->coord[i1].y;
129         x2 = tri->coord[i2].x, y2 = tri->coord[i2].y;
130         
131         // test for easy cases, else split trinagle in two and render both halfs
132         if (y1 == y2) {
133                 if (x1 > x2) swap(&x1, &x2);
134                 add_flat_triangle(image, x1, y1, x2, y2, x0, y0,
135                                   tri->mult, tri->add);
136         } else if (y0 == y1) {
137                 if (x0 > x1) swap(&x0, &x1);
138                 add_flat_triangle(image, x0, y0, x1, y1, x2, y2,
139                                   tri->mult, tri->add);
140         } else {
141                 // compute x pos of the vert that builds the splitting line with x1
142                 int tmp_x = x0 + (int)(0.5f + (float)(y1-y0) * (float)(x2-x0) / (float)(y2-y0));
143  
144                 if (x1 > tmp_x) swap(&x1, &tmp_x);
145                 add_flat_triangle(image, x1, y1, tmp_x, y1, x0, y0,
146                                   tri->mult, tri->add);
147                 add_flat_triangle(image, x1, y1, tmp_x, y1, x2, y2,
148                                   tri->mult, tri->add);
149         }
150 }
151
152 /* Create a new image, allocated off context. */
153 static struct image *new_image(const void *ctx,
154                                unsigned width, unsigned height, unsigned stride)
155 {
156         struct image *image = talloc(ctx, struct image);
157
158         image->width = width;
159         image->height = height;
160         image->stride = stride;
161         image->buffer = talloc_zero_array(image, unsigned char,
162                                           stride * height);
163         return image;
164 }
165
166 /* Taken from JPEG example code.  Quality is 1 to 100. */
167 static void write_jpeg_file(const struct image *image,
168                             const char *filename, int quality)
169 {
170         struct jpeg_compress_struct cinfo;
171         struct jpeg_error_mgr jerr;
172         FILE *outfile;
173         JSAMPROW row_pointer[1];
174         int row_stride;
175
176         cinfo.err = jpeg_std_error(&jerr);
177         jpeg_create_compress(&cinfo);
178
179         if ((outfile = fopen(filename, "wb")) == NULL)
180                 err(1, "can't open %s", filename);
181
182         jpeg_stdio_dest(&cinfo, outfile);
183
184         cinfo.image_width = image->width;
185         cinfo.image_height = image->height;
186         cinfo.input_components = 3;
187         cinfo.in_color_space = JCS_RGB;
188         jpeg_set_defaults(&cinfo);
189         jpeg_set_quality(&cinfo, quality, TRUE);
190
191         jpeg_start_compress(&cinfo, TRUE);
192         row_stride = image->width * 3;
193
194         while (cinfo.next_scanline < cinfo.image_height) {
195                 row_pointer[0] = image->buffer + cinfo.next_scanline*row_stride;
196                 (void) jpeg_write_scanlines(&cinfo, row_pointer, 1);
197         }
198
199         jpeg_finish_compress(&cinfo);
200         fclose(outfile);
201
202         jpeg_destroy_compress(&cinfo);
203 }
204
205 static struct image *read_jpeg_file(const void *ctx, const char *filename)
206 {
207         struct jpeg_decompress_struct cinfo;
208         struct image *image;
209         struct jpeg_error_mgr jerr;
210         FILE *infile;
211         int row_stride;
212
213         if ((infile = fopen(filename, "rb")) == NULL)
214                 err(1, "can't open %s", filename);
215
216         cinfo.err = jpeg_std_error(&jerr);
217
218         jpeg_create_decompress(&cinfo);
219
220         jpeg_stdio_src(&cinfo, infile);
221
222         jpeg_read_header(&cinfo, TRUE);
223
224         jpeg_start_decompress(&cinfo);
225         row_stride = cinfo.output_width * cinfo.output_components;
226
227         image = new_image(ctx,
228                           cinfo.output_width, cinfo.output_height, row_stride);
229         while (cinfo.output_scanline < cinfo.output_height) {
230                 JSAMPROW row = &image->buffer[cinfo.output_scanline*row_stride];
231                 jpeg_read_scanlines(&cinfo, &row, 1);
232         }
233
234         (void) jpeg_finish_decompress(&cinfo);
235         jpeg_destroy_decompress(&cinfo);
236         fclose(infile);
237         return image;
238 }
239
240 /* Higher means closer to perfect match.  We assume images same size. */
241 static unsigned long compare_images(const struct image *a,
242                                     const struct image *b)
243 {
244         unsigned long result = 0;
245         unsigned i;
246
247         /* Huge images won't work here.  We'd need to get cleverer. */
248         assert(a->height * a->stride < ULONG_MAX / 8);
249
250         for (i = 0; i < a->height * a->stride; i++) {
251                 if (a->buffer[i] > b->buffer[i])
252                         result += a->buffer[i] - b->buffer[i];
253                 else
254                         result += b->buffer[i] - a->buffer[i];
255         }
256         return result;
257 }
258
259 /* Precalculate the alpha adds and multiplies for this color/alpha combo. */
260 static void calc_multipliers(struct triangle *tri)
261 {
262         /* Multiply by 255 - alpha. */
263         tri->mult = (255 - tri->color[3]);
264         /* Add alpha * color */
265         tri->add[0] = (tri->color[0] * tri->color[3]);
266         tri->add[1] = (tri->color[1] * tri->color[3]);
267         tri->add[2] = (tri->color[2] * tri->color[3]);
268 }
269
270 /* Render the image of this drawing, and return it. */
271 static struct image *image_of_drawing(const void *ctx,
272                                       const struct drawing *drawing,
273                                       const struct image *master)
274 {
275         struct image *image;
276         unsigned int i;
277
278         image = new_image(ctx, master->width, master->height, master->stride);
279
280         for (i = 0; i < drawing->num_tris; i++)
281                 paint_triangle(image, &drawing->tri[i]);
282         return image;
283 }
284
285 /* Render the image and compare with the master. */
286 static void score_drawing(struct drawing *drawing,
287                           const struct image *master)
288 {
289         struct image *image;
290
291         /* We don't allocate it off the drawing, since we don't need
292          * it inside the shared area. */
293         image = image_of_drawing(NULL, drawing, master);
294         drawing->score = compare_images(image, master);
295         talloc_free(image);
296 }
297
298 /* Create a new drawing allocated off context (which is the antithread
299  * pool context, so this is all allocated inside the pool so the
300  * antithreads can access it).
301  */
302 static struct drawing *new_drawing(const void *ctx, unsigned int num_tris)
303 {
304         struct drawing *drawing = talloc_zero(ctx, struct drawing);
305         drawing->num_tris = num_tris;
306         drawing->tri = talloc_array(drawing, struct triangle, num_tris);
307         return drawing;
308 }
309
310 /* Make a random change to the drawing: frob one triangle. */
311 static void mutate_drawing(struct drawing *drawing,
312                            const struct image *master)
313 {
314         unsigned int i, r = random();
315         struct triangle *tri = &drawing->tri[r % drawing->num_tris];
316
317         r /= drawing->num_tris;
318         r %= 12;
319         if (r < 6) {
320                 /* Move one corner in x or y dir. */
321                 if (r % 2)
322                         tri->coord[r/2].x = random() % master->width;
323                 else
324                         tri->coord[r/2].y = random() % master->height;
325         } else if (r < 10) {
326                 /* Change one aspect of color. */
327                 tri->color[r - 6] = random() % 256;
328         } else if (r == 10) {
329                 /* Completely move a triangle. */
330                 for (i = 0; i < 3; i++) {
331                         tri->coord[i].x = random() % master->width;
332                         tri->coord[i].y = random() % master->height;
333                 }
334         } else {
335                 /* Completely change a triangle's colour. */
336                 for (i = 0; i < 4; i++)
337                         tri->color[i] = random() % 256;
338         }
339         calc_multipliers(tri);
340 }
341
342 /* Breed two drawings together, and throw in a mutation. */
343 static struct drawing *breed_drawing(const void *ctx,
344                                      const struct drawing *a,
345                                      const struct drawing *b,
346                                      const struct image *master)
347 {
348         unsigned int i;
349         struct drawing *drawing;
350         unsigned int r = random(), randmax = RAND_MAX;
351
352         assert(a->num_tris == b->num_tris);
353         drawing = new_drawing(ctx, a->num_tris);
354
355         for (i = 0; i < a->num_tris; i++) {
356                 switch (r & 1) {
357                 case 0:
358                         /* Take from A. */
359                         drawing->tri[i] = a->tri[i];
360                         break;
361                 case 1:
362                         /* Take from B. */
363                         drawing->tri[i] = b->tri[i];
364                         break;
365                 }
366                 r >>= 1;
367                 randmax >>= 1;
368                 if (randmax == 0) {
369                         r = random();
370                         randmax = RAND_MAX;
371                 }
372         }
373         mutate_drawing(drawing, master);
374         score_drawing(drawing, master);
375         return drawing;
376 }
377
378 /* This is our anti-thread.  It does the time-consuming operation of
379  * breeding two drawings together and scoring the result. */
380 static void *breeder(struct at_pool *atp, const struct image *master)
381 {
382         const struct drawing *a, *b;
383
384         /* For simplicity, controller just hands us two pointers in
385          * separate writes.  It could put them in the pool for us to
386          * read. */
387         while ((a = at_read_parent(atp)) != NULL) {
388                 struct drawing *child;
389                 b = at_read_parent(atp);
390
391                 child = breed_drawing(at_pool_ctx(atp), a, b, master);
392                 at_tell_parent(atp, child);
393         }
394         /* Unused: we never exit. */
395         return NULL;
396 }
397
398 /* We keep a very rough count of how much work each athread has.  This
399  * works fine since fairly all rendering takes about the same time.
400  *
401  * Better alternative would be to put all the pending work somewhere
402  * in the shared area and notify any idle thread.  The threads would
403  * keep looking in that shared area until they can't see any more
404  * work, then they'd at_tell_parent() back. */
405 struct athread_work {
406         struct athread *at;
407         unsigned int pending;
408 };
409
410 /* It's assumed that there isn't more than num results pending. */
411 static unsigned gather_results(struct athread_work *athreads,
412                                unsigned int num_threads,
413                                struct drawing **drawing,
414                                unsigned int num,
415                                bool block)
416 {
417         unsigned int i, maxfd = 0, done = 0;
418         struct timeval zero = { .tv_sec = 0, .tv_usec = 0 };
419
420         /* If it mattered, we could cache this fd mask and maxfd. */
421         for (i = 0; i < num_threads; i++) {
422                 if (at_fd(athreads[i].at) > maxfd)
423                         maxfd = at_fd(athreads[i].at);
424         }
425
426         do {
427                 fd_set set;
428                 FD_ZERO(&set);
429                 for (i = 0; i < num_threads; i++)
430                         FD_SET(at_fd(athreads[i].at), &set);
431
432                 if (select(maxfd+1, &set, NULL, NULL, block ? NULL : &zero) < 0)
433                         err(1, "Selecting on antithread results");
434
435                 for (i = 0; i < num_threads; i++) {
436                         if (!FD_ISSET(at_fd(athreads[i].at), &set))
437                                 continue;
438                         *drawing = at_read(athreads[i].at);
439                         if (!*drawing)
440                                 err(1, "Error with thread %u", i);
441                         drawing++;
442                         num--;
443                         athreads[i].pending--;
444                         done++;
445                 }
446         } while (block && num);
447
448         return done;
449 }
450
451 /* Hand work to an antithread to breed these two together. */
452 static void tell_some_breeder(struct athread_work *athreads,
453                               unsigned int num_threads,
454                               const struct drawing *a, const struct drawing *b)
455 {
456         unsigned int i, best = 0;
457
458         /* Find least loaded thread. */
459         for (i = 1; i < num_threads; i++) {
460                 if (athreads[i].pending < athreads[best].pending)
461                         best = i;
462         }
463
464         at_tell(athreads[best].at, a);
465         at_tell(athreads[best].at, b);
466         athreads[best].pending++;
467 }
468
469 /* We seed initial triangles colours from the master image. */
470 static const unsigned char *initial_random_color(const struct image *master)
471 {
472         return master->buffer + (random() % (master->height * master->width))*3;
473 }
474
475 /* Create an initial random drawing. */
476 static struct drawing *random_drawing(const void *ctx,
477                                       const struct image *master,
478                                       unsigned int num_tris)
479 {
480         struct drawing *drawing = new_drawing(ctx, num_tris);
481         unsigned int i;
482
483         for (i = 0; i < drawing->num_tris; i++) {
484                 unsigned int c;
485                 struct triangle *tri = &drawing->tri[i];
486                 for (c = 0; c < 3; c++) {
487                         tri->coord[c].x = random() % master->width;
488                         tri->coord[c].y = random() % master->height;
489                 }
490                 memcpy(tri->color, initial_random_color(master), 3);
491                 tri->color[3] = (random() % 255) + 1;
492                 calc_multipliers(tri);
493         }
494         score_drawing(drawing, master);
495         return drawing;
496 }
497
498 /* Read in a drawing from the saved state file. */
499 static struct drawing *read_drawing(const void *ctx, FILE *in,
500                                     const struct image *master)
501 {
502         struct drawing *drawing;
503         unsigned int i;
504
505         if (fscanf(in, "%u triangles:\n", &i) != 1)
506                 errx(1, "Reading saved state");
507         drawing = new_drawing(ctx, i);
508         for (i = 0; i < drawing->num_tris; i++) {
509                 unsigned int color[4];
510                 if (fscanf(in, "%u,%u,%u,%u,%u,%u,%u,%u,%u,%u\n",
511                            &drawing->tri[i].coord[0].x,
512                            &drawing->tri[i].coord[0].y,
513                            &drawing->tri[i].coord[1].x,
514                            &drawing->tri[i].coord[1].y,
515                            &drawing->tri[i].coord[2].x,
516                            &drawing->tri[i].coord[2].y,
517                            &color[0], &color[1], &color[2], &color[3]) != 10)
518                         errx(1, "Reading saved state");
519                 drawing->tri[i].color[0] = color[0];
520                 drawing->tri[i].color[1] = color[1];
521                 drawing->tri[i].color[2] = color[2];
522                 drawing->tri[i].color[3] = color[3];
523                 calc_multipliers(&drawing->tri[i]);
524         }
525         score_drawing(drawing, master);
526         return drawing;
527 }
528
529 /* Comparison function for sorting drawings best to worst. */
530 static int compare_drawing_scores(const void *_a, const void *_b)
531 {
532         struct drawing **a = (void *)_a, **b = (void *)_b;
533
534         return (*a)->score - (*b)->score;
535 }
536
537 /* Save one drawing to state file */
538 static void dump_drawings(struct drawing **drawing, const char *outname)
539 {
540         FILE *out;
541         unsigned int i, j;
542         char *tmpout = talloc_asprintf(NULL, "%s.tmp", outname);
543
544         out = fopen(tmpout, "w");
545         if (!out)
546                 err(1, "Opening %s", tmpout);
547         fprintf(out, "POPULATION_SIZE=%u\n", POPULATION_SIZE);
548         for (i = 0; i < POPULATION_SIZE; i++) {
549                 fprintf(out, "%u triangles:\n", drawing[i]->num_tris);
550                 for (j = 0; j < drawing[i]->num_tris; j++) {
551                         fprintf(out, "%u,%u,%u,%u,%u,%u,%u,%u,%u,%u\n",
552                                 drawing[i]->tri[j].coord[0].x,
553                                 drawing[i]->tri[j].coord[0].y,
554                                 drawing[i]->tri[j].coord[1].x,
555                                 drawing[i]->tri[j].coord[1].y,
556                                 drawing[i]->tri[j].coord[2].x,
557                                 drawing[i]->tri[j].coord[2].y,
558                                 drawing[i]->tri[j].color[0],
559                                 drawing[i]->tri[j].color[1],
560                                 drawing[i]->tri[j].color[2],
561                                 drawing[i]->tri[j].color[3]);
562                 }
563         }
564         if (fclose(out) != 0)
565                 err(1, "Failure closing %s", tmpout);
566
567         if (rename(tmpout, outname) != 0)
568                 err(1, "Renaming %s over %s", tmpout, outname);
569         talloc_free(tmpout);
570 }
571
572 /* Save state file. */
573 static void dump_state(struct drawing *drawing[POPULATION_SIZE],
574                        const struct image *master,
575                        const char *outpic,
576                        const char *outstate,
577                        unsigned int gen)
578 {
579         char *out = talloc_asprintf(NULL, "%s.%08u.jpg", outpic, gen);
580         struct image *image;
581         printf("Dumping gen %u to %s & %s\n", gen, out, outstate);
582         dump_drawings(drawing, outstate);
583         image = image_of_drawing(out, drawing[0], master);
584         write_jpeg_file(image, out, 80);
585         talloc_free(out);
586 }
587
588 /* Biassed coinflip moves us towards top performers.  I didn't spend
589  * too much time on it, but 1/32 seems to give decent results (see
590  * breeding-algos.gnumeric). */
591 static struct drawing *select_good_drawing(struct drawing *drawing[],
592                                            unsigned int population)
593 {
594         if (population == 1)
595                 return drawing[0];
596         if (random() % 32)
597                 return select_good_drawing(drawing, population/2);
598         return select_good_drawing(drawing + population/2, population/2);
599 }
600
601 static void usage(void)
602 {
603         errx(1, "usage: <infile> <outfile> <statefile> <numtriangles> <numcpus> [<instatefile>]");
604 }
605
606 int main(int argc, char *argv[])
607 {
608         struct image *master;
609         unsigned int gen, since_prev_best, num_threads, i;
610         struct drawing *drawing[POPULATION_SIZE];
611         unsigned long prev_best, poolsize;
612         struct at_pool *atp;
613         struct athread_work *athreads;
614
615         if (argc != 6 && argc != 7)
616                 usage();
617
618         /* Room for triangles and master image, with some spare.
619          * We should really read master image header first, so we can be
620          * more precise than "about 3MB".  ccan/alloc also needs some 
621          * more work to be more efficient. */
622         poolsize = (POPULATION_SIZE + POPULATION_SIZE/4) * (sizeof(struct drawing) + atoi(argv[4]) * sizeof(struct triangle)) * 2 + 1000 * 1000 * 3;
623         atp = at_pool(poolsize);
624         if (!atp)
625                 err(1, "Creating pool of %lu bytes", poolsize);
626
627         /* Auto-free the pool and anything hanging off it (eg. threads). */
628         talloc_steal(talloc_autofree_context(), atp);
629
630         /* Read in file */
631         master = read_jpeg_file(at_pool_ctx(atp), argv[1]);
632
633         if (argc == 6) {
634                 printf("Creating initial population");
635                 fflush(stdout);
636                 for (i = 0; i < POPULATION_SIZE; i++) {
637                         drawing[i] = random_drawing(at_pool_ctx(atp),
638                                                     master, atoi(argv[4]));
639                         printf(".");
640                         fflush(stdout);
641                 }
642                 printf("\n");
643         } else {
644                 FILE *state;
645                 char header[100];
646                 state = fopen(argv[6], "r");
647                 if (!state)
648                         err(1, "Opening %s", argv[6]);
649                 fflush(stdout);
650                 fgets(header, 100, state);
651                 printf("Loading initial population from %s: %s", argv[6],
652                         header);
653                 for (i = 0; i < POPULATION_SIZE; i++) {
654                         drawing[i] = read_drawing(at_pool_ctx(atp),
655                                                   state, master);
656                         printf(".");
657                         fflush(stdout);
658                 }
659         }
660
661         num_threads = atoi(argv[5]);
662         if (!num_threads)
663                 usage();
664
665         /* Hang the threads off the pool (not *in* the pool). */
666         athreads = talloc_array(atp, struct athread_work, num_threads);
667         for (i = 0; i < num_threads; i++) {
668                 athreads[i].pending = 0;
669                 athreads[i].at = at_run(atp, breeder, master);
670                 if (!athreads[i].at)
671                         err(1, "Creating antithread %u", i);
672         }
673
674         since_prev_best = 0;
675         /* Worse than theoretically worst case. */
676         prev_best = master->height * master->stride * 256;
677
678         for (gen = 0; since_prev_best < PLATEAU_GENS; gen++) {
679                 unsigned int j, done = 0;
680                 struct drawing *new[POPULATION_SIZE/4];
681
682                 qsort(drawing, POPULATION_SIZE, sizeof(drawing[0]),
683                       compare_drawing_scores);
684
685                 printf("Best %lu, worst %lu\n",
686                        drawing[0]->score, drawing[POPULATION_SIZE-1]->score);
687
688                 /* Probability of being chosen to breed depends on
689                  * rank.  We breed over lowest 1/4 population. */
690                 for (j = 0; j < POPULATION_SIZE / 4; j++) {
691                         struct drawing *best1, *best2;
692
693                         best1 = select_good_drawing(drawing, POPULATION_SIZE);
694                         best2 = select_good_drawing(drawing, POPULATION_SIZE);
695
696                         tell_some_breeder(athreads, num_threads, best1, best2);
697
698                         /* We reap during loop, so return pipes don't fill.
699                          * See "Better alternative" above. */
700                         done += gather_results(athreads, num_threads,
701                                                new + done, j - done, false);
702                 }
703
704                 /* Collate final results. */
705                 gather_results(athreads, num_threads, new+done, j-done, true);
706
707                 /* Overwrite bottom 1/4 */
708                 for (j = POPULATION_SIZE * 3 / 4; j < POPULATION_SIZE; j++) {
709                         talloc_free(drawing[j]);
710                         drawing[j] = new[j - POPULATION_SIZE * 3 / 4];
711                 }
712
713                 /* We dump on every 1% improvement in score. */
714                 if (drawing[0]->score < prev_best * 0.99) {
715 #ifndef BENCHMARK
716                         dump_state(drawing, master, argv[2], argv[3], gen);
717 #endif
718                         prev_best = drawing[0]->score;
719                         since_prev_best = 0;
720                 } else
721                         since_prev_best++;
722
723 #ifdef BENCHMARK
724                 if (gen == 100)
725                         exit(0);
726 #endif
727         }
728
729         /* Dump final state */
730         printf("No improvement over %lu for %u gens\n",
731                prev_best, since_prev_best);
732         dump_state(drawing, master, argv[2], argv[3], gen);
733         return 0;
734 }