w2v-server.pl - ids-kl/derekovecs - Gitiles

 #!/usr/local/bin/perl
 use Inline C;
 use Inline C => Config => CLEAN_AFTER_BUILD => 0, ccflags => $Config{ccflags}." -O4";
 #use Inline C => Config => BUILD_NOISY => 1, CFLAGS => $Config{cflags}." -O4 -mtune k9";
 #use Inline C => Config => CLEAN_AFTER_BUILD => 0, ccflags => $Config{ccflags}." -Ofast -march k8 -mtune k8 ";
 use Mojolicious::Lite;
 use Mojo::JSON qw(decode_json encode_json to_json);
 use Encode qw(decode encode);
 use Getopt::Std;
 use Mojo::Server::Daemon;
 use Cwd;
 app->static->paths->[0] = getcwd;

 plugin 'Log::Access';
 plugin "RequestBase";

 our $opt_i = 0; # latin1-input?
 our $opt_l = undef;
 our $opt_p = 5676;
 our $opt_m;
 our $opt_M;
 our $opt_n = '';
 our $opt_d;
 our $opt_G;

 my %marked;
 my $training_args="";
 my $mergedEnd=0;
 my %cache;

 getopts('d:Gil:p:m:n:M:');

 if($opt_M) {
   open my $handle, '<:encoding(UTF-8)', $opt_M
     or die "Can't open '$opt_M' for reading: $!";
   while(<$handle>) {
     foreach my $mw (split /\s+/) {
       $marked{$mw}=1
     }
   }
   close($handle);
 }

 # -cbow 1 -size 200 -window 8 -negative 25 -hs 0 -sample 1e-4 -threads 40 -binary 1 -iter 15
 if(!$ARGV[0]) {
   init_net("vectors15.bin", $opt_n, ($opt_i? 1 : 0));
 } else {
   init_net($ARGV[0], $opt_n, ($opt_i? 1 : 0));
   if(open(FILE, "$ARGV[0].args")) {
     $training_args = <FILE>;
   }
   close(FILE);
 }

 if($opt_m) {
   $mergedEnd = mergeVectors($opt_m);
 }


 if($opt_d) { # -d: dump  vecs and exit
 	dump_vecs($opt_d);
 	exit;
 }

 my $daemon = Mojo::Server::Daemon->new(
     app    => app,
     listen => ['http://'.($opt_l ? $opt_l : '*').":$opt_p"]
 );

 if($opt_G) {
   print "Filtering garbage\n";
   filter_garbage();
 }

 get '/derekovecs/js/*' => sub {
 	my $c = shift;
 	my $url = $c->req->url;
 	$url =~ s@/derekovecs@@g;
   $c->app->log->info("GET: " . $url);
 	$c->reply->static($url);
 };

 get '/' => sub {
   my $c    = shift;
   $c->app->log->info("get: ".$c->req->url->to_abs);
 	my $word=$c->param('word');
   my $no_nbs=$c->param('n') || 100;
   my $no_iterations=$c->param('N') || 2000;
   my $perplexity=$c->param('perplexity') || 20;
   my $epsilon=$c->param('epsilon') || 5;
   my $som=$c->param('som') || 0;
 	my $searchBaseVocabFirst=$c->param('sbf') || 0;
   my $sort=$c->param('sort') || 0;
   my $json=$c->param('json') || 0;
   my $res;
 	my @lists;
 	my @collocations;
 	if(defined($word) && $word !~ /^\s*$/) {
 		$c->inactivity_timeout(300);
 		$word =~ s/\s+/ /g;
     for my $w (split(' *\| *', $word)) {
       if ($cache{$w}) {
         $c->app->log->info("Getting $w results from cache");
         $res = $cache{$w}
       } else {
         $c->app->log->info('Looking for neighbours of '.$w);
         if($opt_i) {
           $res = get_neighbours(encode("iso-8859-1", $w), $no_nbs, $sort, $searchBaseVocabFirst);
         } else {
           $res = get_neighbours($w, $no_nbs, $sort, $searchBaseVocabFirst);
         }
         $cache{$w} = $res;
       }
       push(@lists, $res->{paradigmatic});
     }
   }
 	$word =~ s/ *\| */ | /g;
   if($json) {
     return $c->render(json => {word => $word, list => \@lists, collocators=>$res->{syntagmatic}});
   } else {
     $c->render(template=>"index", word=>$word, no_nbs=>$no_nbs, no_iterations => $no_iterations, epsilon=> $epsilon, perplexity=> $perplexity, show_som=>$som, searchBaseVocabFirst=>$searchBaseVocabFirst, sort=>$sort, training_args=>$training_args, mergedEnd=> $mergedEnd, marked=>\%marked, lists=> \@lists, collocators=> $res->{syntagmatic});
   }
 };

 $daemon->run; # app->start;

 exit;

 __END__

 __C__
 #include <stdio.h>
 #include <string.h>
 #include <math.h>
 #include <malloc.h>
 #include <stdlib.h>    //strlen
 #include <sys/mman.h>
 #include <pthread.h>

 #define max_size 2000
 #define max_w 50
 #define MAX_NEIGHBOURS 1000
 #define MAX_WORDS -1
 #define MAX_THREADS 100
 #define MAX_CC 50
 #define EXP_TABLE_SIZE 1000
 #define MAX_EXP 6
 #define MIN_RESP 0.50

 //the thread function
 void *connection_handler(void *);

 typedef struct {
 	long long *index;
 	float *dist;
 	float *norm;
   long long *pos;
 	int length;
 } knn;

 typedef struct {
   long long wordi[MAX_NEIGHBOURS];
   char sep[MAX_NEIGHBOURS];
   int length;
 } wordlist;

 typedef struct {
   wordlist *wl;
 	char *token;
 	int N;
 	long from;
 	unsigned long upto;
   float *target_sums;
 } knnpars;

 float *M, *M2=0L, *syn1neg_window, *expTable;
 char *vocab;
 char *garbage = NULL;

 long long words, size, merged_end;
 long long merge_words = 0;
 int num_threads=20;
 int latin_enc=0;
 int window;

 int init_net(char *file_name, char *net_name, int latin) {
   FILE *f, *binvecs, *binwords;
 	int binwords_fd, binvecs_fd, net_fd, i;
 	long long a, b, c, d, cn;
 	float len;
   double val;

 	char binvecs_fname[256], binwords_fname[256];
 	strcpy(binwords_fname, file_name);
 	strcat(binwords_fname, ".words");
 	strcpy(binvecs_fname, file_name);
 	strcat(binvecs_fname, ".vecs");

   latin_enc = latin;
   f = fopen(file_name, "rb");
   if (f == NULL) {
     printf("Input file %s not found\n", file_name);
     return -1;
   }
   fscanf(f, "%lld", &words);
 	if(MAX_WORDS > 0 && words > MAX_WORDS) words = MAX_WORDS;
   fscanf(f, "%lld", &size);
 	if( (binvecs_fd = open(binvecs_fname, O_RDONLY)) < 0  || (binwords_fd = open(binwords_fname, O_RDONLY)) < 0) {
     printf("Converting %s to memory mappable structures\n", file_name);
 		vocab = (char *)malloc((long long)words * max_w * sizeof(char));
 		M = (float *)malloc((long long)words * (long long)size * sizeof(float));
 		if (M == NULL) {
 			printf("Cannot allocate memory: %lld MB    %lld  %lld\n", (long long)words * size * sizeof(float) / 1048576, words, size);
 			return -1;
 		}
     if(strstr(file_name, ".txt")) {
       for (b = 0; b < words; b++) {
         a = 0;
         while (1) {
           vocab[b * max_w + a] = fgetc(f);
           if (feof(f) || (vocab[b * max_w + a] == ' ')) break;
           if ((a < max_w) && (vocab[b * max_w + a] != '\n')) a++;
         }
         vocab[b * max_w + a] = 0;
         len = 0;
         for (a = 0; a < size; a++) {
           fscanf(f, "%lf", &val);
           M[a + b * size] = val;
           len += val * val;
         }
         len = sqrt(len);
         for (a = 0; a < size; a++) M[a + b * size] /= len;
       }
     } else {
       for (b = 0; b < words; b++) {
         a = 0;
         while (1) {
           vocab[b * max_w + a] = fgetc(f);
           if (feof(f) || (vocab[b * max_w + a] == ' ')) break;
           if ((a < max_w) && (vocab[b * max_w + a] != '\n')) a++;
         }
         vocab[b * max_w + a] = 0;
         fread(&M[b * size], sizeof(float), size, f);
         len = 0;
         for (a = 0; a < size; a++) len += M[a + b * size] * M[a + b * size];
         len = sqrt(len);
         for (a = 0; a < size; a++) M[a + b * size] /= len;
       }
     }
 		if( (binvecs = fopen(binvecs_fname, "wb")) != NULL && (binwords = fopen(binwords_fname, "wb")) != NULL) {
 			fwrite(M, sizeof(float), (long long)words * (long long)size, binvecs);
 			fclose(binvecs);
 			fwrite(vocab, sizeof(char), (long long)words * max_w, binwords);
 			fclose(binwords);
 		}
   }
 	if( (binvecs_fd = open(binvecs_fname, O_RDONLY)) >= 0 && (binwords_fd = open(binwords_fname, O_RDONLY)) >= 0) {
 		M = mmap(0, sizeof(float) * (long long)words * (long long)size, PROT_READ, MAP_SHARED, binvecs_fd, 0);
 		vocab = mmap(0,  sizeof(char) * (long long)words * max_w, PROT_READ, MAP_SHARED, binwords_fd, 0);
     if (M == MAP_FAILED || vocab == MAP_FAILED) {
 			close(binvecs_fd);
 			close(binwords_fd);
 			fprintf(stderr, "Cannot mmap %s or %s\n", binwords_fname, binvecs_fname);
 			exit(-1);
     }
 	} else {
     fprintf(stderr, "Cannot open %s or %s\n", binwords_fname, binvecs_fname);
     exit(-1);
 	}
   fclose(f);

   if(net_name && strlen(net_name) > 0) {
     if( (net_fd = open(net_name, O_RDONLY)) >= 0) {
       window = (lseek(net_fd, 0, SEEK_END) -  sizeof(float) * words * size) / words / size / sizeof(float) / 2;
       //      lseek(net_fd, sizeof(float) * words * size, SEEK_SET);
       // munmap(M,  sizeof(float) * words * size);
       M2 = mmap(0, sizeof(float) * words * size + sizeof(float) * 2 * window * size * words, PROT_READ, MAP_SHARED, net_fd, 0);
       if (M2 == MAP_FAILED) {
         close(net_fd);
         fprintf(stderr, "Cannot mmap %s\n", net_name);
         exit(-1);
       }
       syn1neg_window =  M2 + words * size;
     } else {
       fprintf(stderr, "Cannot open %s\n", net_name);
       exit(-1);
     }
     fprintf(stderr, "Successfully memmaped %s. Determined window size: %d\n", net_name, window);
   }

 	expTable = (float *) malloc((EXP_TABLE_SIZE + 1) * sizeof(float));
 	for (i = 0; i < EXP_TABLE_SIZE; i++) {
 		expTable[i] = exp((i / (float) EXP_TABLE_SIZE * 2 - 1) * MAX_EXP); // Precompute the exp() table
 		expTable[i] = expTable[i] / (expTable[i] + 1); // Precompute f(x) = x / (x + 1)
 	}
 	return 0;
 }

 long mergeVectors(char *file_name){
   FILE *f, *binvecs, *binwords;
 	int binwords_fd, binvecs_fd, net_fd, i;
 	long long a, b, c, d, cn;
 	float len;
   float *merge_vecs;
   char *merge_vocab;
  /*  long long merge_words, merge_size; */
   long long merge_size;

 	char binvecs_fname[256], binwords_fname[256];
 	strcpy(binwords_fname, file_name);
 	strcat(binwords_fname, ".words");
 	strcpy(binvecs_fname, file_name);
 	strcat(binvecs_fname, ".vecs");

   f = fopen(file_name, "rb");
   if (f == NULL) {
     printf("Input file %s not found\n", file_name);
     exit -1;
   }
   fscanf(f, "%lld", &merge_words);
   fscanf(f, "%lld", &merge_size);
   if(merge_size != size){
 		fprintf(stderr, "vectors must have the same length\n");
 		exit(-1);
 	}
 	if( (binvecs_fd = open(binvecs_fname, O_RDONLY)) >= 0 && (binwords_fd = open(binwords_fname, O_RDONLY)) >= 0) {
 		merge_vecs = malloc(sizeof(float) * (words + merge_words) * size);
 		merge_vocab = malloc(sizeof(char) * (words + merge_words) * max_w);
     if (merge_vecs == NULL || merge_vocab == NULL) {
 			close(binvecs_fd);
 			close(binwords_fd);
 			fprintf(stderr, "Cannot reserve memory for %s or %s\n", binwords_fname, binvecs_fname);
 			exit(-1);
     }
     read(binvecs_fd, merge_vecs, merge_words * size * sizeof(float));
     read(binwords_fd, merge_vocab, merge_words * max_w);
 	} else {
     fprintf(stderr, "Cannot open %s or %s\n", binwords_fname, binvecs_fname);
     exit(-1);
 	}
 	printf("Successfully reallocated memory\nMerging...\n");
 	fflush(stdout);
   memcpy(merge_vecs + merge_words * size, M, words * size * sizeof(float));
   memcpy(merge_vocab + merge_words * max_w, vocab, words * max_w);
   munmap(M, words * size * sizeof(float));
   munmap(vocab, words * max_w);
   M = merge_vecs;
   vocab = merge_vocab;
   merged_end = merge_words;
   words += merge_words;
   fclose(f);
 	printf("merged_end: %lld, words: %lld\n", merged_end, words);
   return((long) merged_end);
 }

 void filter_garbage() {
   long i;
   unsigned char *w, previous, c;
   garbage = malloc(words);
   memset(garbage, 0, words);
   for (i = 0; i < words; i++) {
     w = vocab + i * max_w;
     previous = 0;
     while((c = *w++) && !garbage[i]) {
       if( ((c <= 90 && c >= 65) && (previous >= 97 && previous <= 122)) ||
           (previous == '-' && (c & 32)) ||
           (previous == 0xc2 && (c == 0xa4 || c == 0xb6 ))
         ) {
         garbage[i]=1;
         continue;
       }
       previous = c;
     }
   }
   return;
 }

 void *getCollocators(knnpars *pars) {
 	int N = pars->N;
   int cc = pars->wl->wordi[0];
 	knn *nbs = NULL;
   long window_layer_size = size * window * 2;
 	long a, b, c, d, e, window_offset, target, max_target=0, maxmax_target;
 	float f, max_f, maxmax_f;
 	float *target_sums, *bestf, *bestn, worstbest, wpos_sum;
 	long long *besti, *bestp;

   if(M2 == NULL || cc == -1)
     return NULL;

 	a = posix_memalign((void **) &target_sums, 128, words * sizeof(float));
 	besti = malloc(N * sizeof(long long));
 	bestp = malloc(N * sizeof(long long));
 	bestf = malloc(N * sizeof(float));
 	bestn = malloc(N * sizeof(float));

   worstbest = MIN_RESP;

   for (b = 0; b < words; b++)
 			target_sums[b]=0;
   for (b = 0; b < N; b++) {
       besti[b] = -1;
       bestn[b] = 1;
       bestf[b] = worstbest;
   }

   d = cc;
   maxmax_f = -1;
   maxmax_target = 0;

   for (a = pars->from; a < pars->upto; a++) {
     if(a >= window)
       a++;
     wpos_sum = 0;
     printf("window pos: %ld\n", a);
     if (a != window) {
       max_f = -1;
       window_offset = a * size;
       if (a > window)
         window_offset -= size;
       for(target = 0; target < words; target ++) {
         if(target == d)
           continue;
         f = 0;
         for (c = 0; c < size; c++)
           f += M2[d* size + c]	* syn1neg_window[target * window_layer_size	+ window_offset + c];
         if (f < -MAX_EXP)
           continue;
         else if (f > MAX_EXP)
           continue;
         else
           f = expTable[(int) ((f + MAX_EXP)	* (EXP_TABLE_SIZE / MAX_EXP / 2))];
         wpos_sum += f;

         target_sums[target] += f;
         if(f > worstbest) {
           for (b = 0; b < N; b++) {
             if (f > bestf[b]) {
 							memmove(bestf + b + 1, bestf + b, (N - b -1) * sizeof(float));
 							memmove(besti + b + 1, besti + b, (N - b -1) * sizeof(long long));
 							memmove(bestp + b + 1, bestp + b, (N - b -1) * sizeof(long long));
 							bestf[b] = f;
 							besti[b] = target;
 							bestp[b] = window-a;
 							break;
             }
           }
           if(b == N - 1)
             worstbest = bestf[N-1];
         }
       }
       printf("%d %.2f\n", max_target, max_f);
       printf("%s (%.2f) ", &vocab[max_target * max_w], max_f);
       if(max_f > maxmax_f) {
         maxmax_f = max_f;
         maxmax_target = max_target;
       }
       for (b = 0; b < N; b++)
         if(bestp[b] == window-a)
           bestn[b] = bestf[b] / wpos_sum;
     } else {
       printf("\x1b[1m%s\x1b[0m ", &vocab[d*max_w]);
     }

   }
   for (b = 0; b < words; b++)
       pars->target_sums[b] += (target_sums[b] / wpos_sum ) / (window * 2);
   free(target_sums);
   for(b=0; b<N && besti[b] >= 0; b++) // THIS LOOP IS NEEDED (b...)
     printf("%s %.2f %d * ", &vocab[besti[b]*max_w], bestf[b], bestp[b]);
   printf("\n");
   nbs = malloc(sizeof(knn));
 	nbs->index = besti;
 	nbs->dist = bestf;
 	nbs->norm = bestn;
 	nbs->pos = bestp;
 	nbs->length = b-1;
   pthread_exit(nbs);
 }

 wordlist *getTargetWords(char *st1, int search_backw) {
   wordlist *wl = malloc(sizeof(wordlist));
   char st[100][max_size], sep[100];
 	long a, b=0, c=0, cn=0;
   int unmerged;

 	while (1) {
 		st[cn][b] = st1[c];
 		b++;
 		c++;
 		st[cn][b] = 0;
 		if (st1[c] == 0) break;
 		if (st1[c] == ' ' || st1[c] == '-') {
       sep[cn++] = st1[c];
 			b = 0;
 			c++;
 		}
 	}
 	cn++;
 	for (a = 0; a < cn; a++) {
 		if(search_backw) {
 			for (b = words - 1; b >= 0; b--) if (!strcmp(&vocab[b * max_w], st[a])) break;
 		}  else {
 			for (b = 0; b < words; b++) if (!strcmp(&vocab[b * max_w], st[a])) break;
 		}
 		if (b == words) b = -1;
 		wl->wordi[a] = b;
 		fprintf(stderr, "Word: \"%s\"  Position in vocabulary: %lld\n", st[a], wl->wordi[a]);
 		if (b == -1) {
 			fprintf(stderr, "Out of dictionary word!\n");
 			cn--;
 			break;
 		}
 	}
   wl->length=cn;
   return(wl);
 }

 void *_get_neighbours(knnpars *pars) {
 	char *st1 = pars->token;
 	int N = pars->N;
 	long from = pars -> from;
 	unsigned long upto = pars -> upto;
 	char file_name[max_size], st[100][max_size], *sep;
 	float dist, len, *bestd, vec[max_size];
 	long long a, b, c, d, cn, *bi, *besti;
 	char ch;
 	knn *nbs = NULL;
   wordlist *wl = pars->wl;

 	besti = malloc(N * sizeof(long long));
 	bestd = malloc(N * sizeof(float));

 	float worstbest=-1;

 	for (a = 0; a < N; a++) bestd[a] = 0;
 	a = 0;
   bi = wl->wordi;
 	cn = wl->length;
   sep = wl->sep;
 	b = bi[0];
 	c = 0;
 	if (b == -1) {
     N = 0;
 	  goto end;
   }
 	for (a = 0; a < size; a++) vec[a] = 0;
 	for (b = 0; b < cn; b++) {
 		if (bi[b] == -1) continue;
     if(b>0 && sep[b-1] == '-')
       for (a = 0; a < size; a++) vec[a] -= M[a + bi[b] * size];
     else
       for (a = 0; a < size; a++) vec[a] += M[a + bi[b] * size];
 	}
 	len = 0;
 	for (a = 0; a < size; a++) len += vec[a] * vec[a];
 	len = sqrt(len);
 	for (a = 0; a < size; a++) vec[a] /= len;
 	for (a = 0; a < N; a++) bestd[a] = -1;
 	for (c = from; c < upto; c++) {
     if(garbage && garbage[c]) continue;
 		a = 0;
 // do not skip taget word
 //		for (b = 0; b < cn; b++) if (bi[b] == c) a = 1;
 //		if (a == 1) continue;
 		dist = 0;
 		for (a = 0; a < size; a++) dist += vec[a] * M[a + c * size];
 		if(dist > worstbest) {
 			for (a = 0; a < N; a++) {
 				if (dist > bestd[a]) {
 					memmove(bestd + a + 1, bestd + a, (N - a -1) * sizeof(float));
 					memmove(besti + a + 1, besti + a, (N - a -1) * sizeof(long long));
 					bestd[a] = dist;
 					besti[a] = c;
 					break;
 				}
 			}
 			worstbest = bestd[N-1];
 		}
 	}

 	nbs = malloc(sizeof(knn));
 	nbs->index = besti;
 	nbs->dist = bestd;
 	nbs->length = N;
 end:
 	pthread_exit(nbs);
 }


 SV *get_neighbours(char *st1, int N, int sort_by, int search_backw) {
   HV *result = newHV();
 	float *target_sums, bestd[MAX_NEIGHBOURS], bestn[MAX_NEIGHBOURS], bests[MAX_NEIGHBOURS], vec[max_size];
 	long long old_words;
 	long besti[MAX_NEIGHBOURS], bestp[MAX_NEIGHBOURS], a, b, c, d, slice;
 	knn *para_nbs[MAX_THREADS];
 	knn *syn_nbs[MAX_THREADS];
 	knnpars pars[MAX_THREADS];
   pthread_t *pt = (pthread_t *)malloc((num_threads+1) * sizeof(pthread_t));
   wordlist *wl;
   int syn_threads = (M2? window * 2 : 0);
   int para_threads = num_threads - syn_threads;

   if(N>MAX_NEIGHBOURS) N=MAX_NEIGHBOURS;


   wl = getTargetWords(st1, search_backw);
   if(wl->length < 1)
     goto end;

 	old_words = words;
   if(merge_words > 0)
 		words = merge_words * 1.25;  /* HACK */
 	slice = words / para_threads;

 	a = posix_memalign((void **) &target_sums, 128, words * sizeof(float));
   for(a = 0; a < words; a++)
     target_sums[a] = 0;

   printf("Starting %d threads\n", para_threads);
   fflush(stdout);
 	for(a=0; a < para_threads; a++) {
 		pars[a].token = st1;
 		pars[a].wl = wl;
 		pars[a].N = N;
 		pars[a].from = a*slice;
 		pars[a].upto = ((a+1)*slice > words? words:(a+1)*slice);
 		pthread_create(&pt[a], NULL, _get_neighbours, (void *) &pars[a]);
 	}
   if(M2) {
     for(a=0; a < syn_threads; a++) {
       pars[a + para_threads].target_sums = target_sums;
       pars[a + para_threads].wl = wl;
       pars[a + para_threads].N = N;
       pars[a + para_threads].from = a;
       pars[a + para_threads].upto = a+1;
       pthread_create(&pt[a + para_threads], NULL, getCollocators, (void *) &pars[a + para_threads]);
     }
   }
   printf("Waiting for para threads to join\n");
   fflush(stdout);
   for (a = 0; a < para_threads; a++) pthread_join(pt[a], &para_nbs[a]);
   printf("Para threads joint\n");
   fflush(stdout);

 	/* if(!syn_nbs[0]) */
 	/* 	goto end; */

 	for(b=0; b < N; b++) {
 		besti[b] = para_nbs[0]->index[b];
 		bestd[b] = para_nbs[0]->dist[b];
 	}

 	for(a=1; a < para_threads; a++) {
 		for(b=0; b < para_nbs[a]->length && para_nbs[a]->index[b] >= 0; b++) {
 			for(c=0; c < N * para_threads; c++) {
 				if(para_nbs[a]->dist[b] > bestd[c]) {
 					for(d=N-1; d>c; d--) {
 						bestd[d] = bestd[d-1];
 						besti[d] = besti[d-1];
 					}
 					besti[c] = para_nbs[a]->index[b];
 					bestd[c] = para_nbs[a]->dist[b];
 					break;
 				}
 			}
 		}
 	}

   AV* array = newAV();
   int i;
   int l1_words=0, l2_words=0;
   for (a = 0, i = 0; i < N && a < 600; a++) {
     long long c = besti[a];
     if(merge_words > 0) {
         if(c >= merge_words) {
             if(l1_words > N / 2)
                 continue;
             else
                 l1_words++;
         } else {
             if(l2_words > N / 2)
                 continue;
             else
                 l2_words++;
         }
     }
     fflush(stdout);
     printf("%s l1:%d l2:%d i:%d a:%ld\n", &vocab[c * max_w], l1_words, l2_words, i, a);

     HV* hash = newHV();
     SV* word = newSVpvf(&vocab[c * max_w], 0);
     if(latin_enc == 0) SvUTF8_on(word);
     fflush(stdout);
     hv_store(hash, "word", strlen("word"), word , 0);
     hv_store(hash, "dist", strlen("dist"), newSVnv(bestd[a]), 0);
     hv_store(hash, "rank", strlen("rank"), newSVuv(besti[a]), 0);
     AV *vector = newAV();
     for (b = 0; b < size; b++) {
       av_push(vector, newSVnv(M[b + besti[a] * size]));
     }
     hv_store(hash, "vector", strlen("vector"), newRV_noinc((SV*)vector), 0);
     av_push(array, newRV_noinc((SV*)hash));
     i++;
   }
   hv_store(result, "paradigmatic", strlen("paradigmatic"), newRV_noinc((SV*)array), 0);

   for(b=0; b < MAX_NEIGHBOURS; b++) {
     besti[b] = -1L;
     bestd[b] = 0;
     bestn[b] = 0;
     bestp[b] = 0;
     bests[b] = 0;
   }

   if (M2) {
     printf("Waiting for syn threads to join\n");
     fflush(stdout);
     for (a = 0; a < syn_threads; a++) pthread_join(pt[a+para_threads], &syn_nbs[a]);
     printf("syn threads joint\n");
     fflush(stdout);

     for(b=0; b < syn_nbs[0]->length; b++) {
       besti[b] = syn_nbs[0]->index[b];
       bestd[b] = syn_nbs[0]->dist[b];
       bestn[b] = syn_nbs[0]->norm[b];
       bestp[b] = syn_nbs[0]->pos[b];
       bests[b] = target_sums[syn_nbs[0]->index[b]];
     }

     if(sort_by != 1) { // sort by responsiveness
       for(a=1; a < syn_threads; a++) {
         for(b=0; b < syn_nbs[a]->length; b++) {
           for(c=0; c < MAX_NEIGHBOURS; c++) {
             if(syn_nbs[a]->dist[b] > bestd[c]) {
               for(d=MAX_NEIGHBOURS-1; d>c; d--) {
                 bestd[d] = bestd[d-1];
                 besti[d] = besti[d-1];
                 bestn[d] = bestn[d-1];
                 bestp[d] = bestp[d-1];
               }
               besti[c] = syn_nbs[a]->index[b];
               bestd[c] = syn_nbs[a]->dist[b];
               bestn[c] = syn_nbs[a]->norm[b];
               bestp[c] = syn_nbs[a]->pos[b];
               break;
             }
           }
         }
       }
     } else { // sort by mean p
       for(a=1; a < syn_threads; a++) {
         for(b=0; b < syn_nbs[a]->length; b++) {
           for(c=0; c < MAX_NEIGHBOURS; c++) {
             if(target_sums[syn_nbs[a]->index[b]] > bests[c]) {
               for(d=MAX_NEIGHBOURS-1; d>c; d--) {
                 bestd[d] = bestd[d-1];
                 besti[d] = besti[d-1];
                 bestn[d] = bestn[d-1];
                 bestp[d] = bestp[d-1];
                 bests[d] = bests[d-1];
               }
               besti[c] = syn_nbs[a]->index[b];
               bestd[c] = syn_nbs[a]->dist[b];
               bestn[c] = syn_nbs[a]->norm[b];
               bestp[c] = syn_nbs[a]->pos[b];
               bests[c] = target_sums[syn_nbs[a]->index[b]];
               break;
             }
           }
         }
       }
     }
     array = newAV();
     for (a = 0; a < MAX_NEIGHBOURS && besti[a] >= 0; a++) {
       HV* hash = newHV();
       SV* word = newSVpvf(&vocab[besti[a] * max_w], 0);
       if(latin_enc == 0) SvUTF8_on(word);
       hv_store(hash, "word", strlen("word"), word , 0);
       hv_store(hash, "dist", strlen("dist"), newSVnv(bestd[a]), 0);
       hv_store(hash, "norm", strlen("norm"), newSVnv(bestn[a]), 0);
       hv_store(hash, "sum", strlen("sum"), newSVnv(target_sums[besti[a]]), 0);
       hv_store(hash, "pos", strlen("pos"), newSVnv(bestp[a]), 0);
       av_push(array, newRV_noinc((SV*)hash));
     }
     hv_store(result, "syntagmatic", strlen("syntagmatic"), newRV_noinc((SV*)array), 0);
   }
 end:
 	words = old_words;
 	return newRV_noinc((SV*)result);
 }

 int dump_vecs(char *fname) {
 	long i, j;
 	FILE *f;
 	/* if(words>200000) */
 	/* 	words=200000; */

 	if((f=fopen(fname, "w")) == NULL) {
 			fprintf(stderr, "cannot open %s for writing\n", fname);
 			return(-1);
 	}
 	fprintf(f, "%lld %lld\n", words, size);
 	for (i=0; i < words; i++) {
 		fprintf(f, "%s ", &vocab[i * max_w]);
 		for(j=0; j < size - 1; j++)
 			fprintf(f, "%f ", M[i*size + j]);
 		fprintf(f, "%f\n", M[i*size + j]);
 	}
 	fclose(f);
 	return(0);
 }
	#!/usr/local/bin/perl
	use Inline C;
	use Inline C => Config => CLEAN_AFTER_BUILD => 0, ccflags => $Config{ccflags}." -O4";
	#use Inline C => Config => BUILD_NOISY => 1, CFLAGS => $Config{cflags}." -O4 -mtune k9";
	#use Inline C => Config => CLEAN_AFTER_BUILD => 0, ccflags => $Config{ccflags}." -Ofast -march k8 -mtune k8 ";
	use Mojolicious::Lite;
	use Mojo::JSON qw(decode_json encode_json to_json);
	use Encode qw(decode encode);
	use Getopt::Std;
	use Mojo::Server::Daemon;
	use Cwd;
	app->static->paths->[0] = getcwd;

	plugin 'Log::Access';
	plugin "RequestBase";

	our $opt_i = 0; # latin1-input?
	our $opt_l = undef;
	our $opt_p = 5676;
	our $opt_m;
	our $opt_M;
	our $opt_n = '';
	our $opt_d;
	our $opt_G;

	my %marked;
	my $training_args="";
	my $mergedEnd=0;
	my %cache;

	getopts('d:Gil:p:m:n:M:');

	if($opt_M) {
	open my $handle, '<:encoding(UTF-8)', $opt_M
	or die "Can't open '$opt_M' for reading: $!";
	while(<$handle>) {
	foreach my $mw (split /\s+/) {
	$marked{$mw}=1
	}
	}
	close($handle);
	}

	# -cbow 1 -size 200 -window 8 -negative 25 -hs 0 -sample 1e-4 -threads 40 -binary 1 -iter 15
	if(!$ARGV[0]) {
	init_net("vectors15.bin", $opt_n, ($opt_i? 1 : 0));
	} else {
	init_net($ARGV[0], $opt_n, ($opt_i? 1 : 0));
	if(open(FILE, "$ARGV[0].args")) {
	$training_args = <FILE>;
	}
	close(FILE);
	}

	if($opt_m) {
	$mergedEnd = mergeVectors($opt_m);
	}


	if($opt_d) { # -d: dump vecs and exit
	dump_vecs($opt_d);
	exit;
	}

	my $daemon = Mojo::Server::Daemon->new(
	app => app,
	listen => ['http://'.($opt_l ? $opt_l : '*').":$opt_p"]
	);

	if($opt_G) {
	print "Filtering garbage\n";
	filter_garbage();
	}

	get '/derekovecs/js/*' => sub {
	my $c = shift;
	my $url = $c->req->url;
	$url =~ s@/derekovecs@@g;
	$c->app->log->info("GET: " . $url);
	$c->reply->static($url);
	};

	get '/' => sub {
	my $c = shift;
	$c->app->log->info("get: ".$c->req->url->to_abs);
	my $word=$c->param('word');
	my $no_nbs=$c->param('n') \|\| 100;
	my $no_iterations=$c->param('N') \|\| 2000;
	my $perplexity=$c->param('perplexity') \|\| 20;
	my $epsilon=$c->param('epsilon') \|\| 5;
	my $som=$c->param('som') \|\| 0;
	my $searchBaseVocabFirst=$c->param('sbf') \|\| 0;
	my $sort=$c->param('sort') \|\| 0;
	my $json=$c->param('json') \|\| 0;
	my $res;
	my @lists;
	my @collocations;
	if(defined($word) && $word !~ /^\s*$/) {
	$c->inactivity_timeout(300);
	$word =~ s/\s+/ /g;
	for my $w (split(' \\| ', $word)) {
	if ($cache{$w}) {
	$c->app->log->info("Getting $w results from cache");
	$res = $cache{$w}
	} else {
	$c->app->log->info('Looking for neighbours of '.$w);
	if($opt_i) {
	$res = get_neighbours(encode("iso-8859-1", $w), $no_nbs, $sort, $searchBaseVocabFirst);
	} else {
	$res = get_neighbours($w, $no_nbs, $sort, $searchBaseVocabFirst);
	}
	$cache{$w} = $res;
	}
	push(@lists, $res->{paradigmatic});
	}
	}
	$word =~ s/ \\| / \| /g;
	if($json) {
	return $c->render(json => {word => $word, list => \@lists, collocators=>$res->{syntagmatic}});
	} else {
	$c->render(template=>"index", word=>$word, no_nbs=>$no_nbs, no_iterations => $no_iterations, epsilon=> $epsilon, perplexity=> $perplexity, show_som=>$som, searchBaseVocabFirst=>$searchBaseVocabFirst, sort=>$sort, training_args=>$training_args, mergedEnd=> $mergedEnd, marked=>\%marked, lists=> \@lists, collocators=> $res->{syntagmatic});
	}
	};

	$daemon->run; # app->start;

	exit;

	__END__

	__C__
	#include <stdio.h>
	#include <string.h>
	#include <math.h>
	#include <malloc.h>
	#include <stdlib.h> //strlen
	#include <sys/mman.h>
	#include <pthread.h>

	#define max_size 2000
	#define max_w 50
	#define MAX_NEIGHBOURS 1000
	#define MAX_WORDS -1
	#define MAX_THREADS 100
	#define MAX_CC 50
	#define EXP_TABLE_SIZE 1000
	#define MAX_EXP 6
	#define MIN_RESP 0.50

	//the thread function
	void connection_handler(void );

	typedef struct {
	long long *index;
	float *dist;
	float *norm;
	long long *pos;
	int length;
	} knn;

	typedef struct {
	long long wordi[MAX_NEIGHBOURS];
	char sep[MAX_NEIGHBOURS];
	int length;
	} wordlist;

	typedef struct {
	wordlist *wl;
	char *token;
	int N;
	long from;
	unsigned long upto;
	float *target_sums;
	} knnpars;

	float M, M2=0L, syn1neg_window, expTable;
	char *vocab;
	char *garbage = NULL;

	long long words, size, merged_end;
	long long merge_words = 0;
	int num_threads=20;
	int latin_enc=0;
	int window;

	int init_net(char file_name, char net_name, int latin) {
	FILE f, binvecs, *binwords;
	int binwords_fd, binvecs_fd, net_fd, i;
	long long a, b, c, d, cn;
	float len;
	double val;

	char binvecs_fname[256], binwords_fname[256];
	strcpy(binwords_fname, file_name);
	strcat(binwords_fname, ".words");
	strcpy(binvecs_fname, file_name);
	strcat(binvecs_fname, ".vecs");

	latin_enc = latin;
	f = fopen(file_name, "rb");
	if (f == NULL) {
	printf("Input file %s not found\n", file_name);
	return -1;
	}
	fscanf(f, "%lld", &words);
	if(MAX_WORDS > 0 && words > MAX_WORDS) words = MAX_WORDS;
	fscanf(f, "%lld", &size);
	if( (binvecs_fd = open(binvecs_fname, O_RDONLY)) < 0 \|\| (binwords_fd = open(binwords_fname, O_RDONLY)) < 0) {
	printf("Converting %s to memory mappable structures\n", file_name);
	vocab = (char )malloc((long long)words max_w * sizeof(char));
	M = (float )malloc((long long)words (long long)size * sizeof(float));
	if (M == NULL) {
	printf("Cannot allocate memory: %lld MB %lld %lld\n", (long long)words * size * sizeof(float) / 1048576, words, size);
	return -1;
	}
	if(strstr(file_name, ".txt")) {
	for (b = 0; b < words; b++) {
	a = 0;
	while (1) {
	vocab[b * max_w + a] = fgetc(f);
	if (feof(f) \|\| (vocab[b * max_w + a] == ' ')) break;
	if ((a < max_w) && (vocab[b * max_w + a] != '\n')) a++;
	}
	vocab[b * max_w + a] = 0;
	len = 0;
	for (a = 0; a < size; a++) {
	fscanf(f, "%lf", &val);
	M[a + b * size] = val;
	len += val * val;
	}
	len = sqrt(len);
	for (a = 0; a < size; a++) M[a + b * size] /= len;
	}
	} else {
	for (b = 0; b < words; b++) {
	a = 0;
	while (1) {
	vocab[b * max_w + a] = fgetc(f);
	if (feof(f) \|\| (vocab[b * max_w + a] == ' ')) break;
	if ((a < max_w) && (vocab[b * max_w + a] != '\n')) a++;
	}
	vocab[b * max_w + a] = 0;
	fread(&M[b * size], sizeof(float), size, f);
	len = 0;
	for (a = 0; a < size; a++) len += M[a + b * size] * M[a + b * size];
	len = sqrt(len);
	for (a = 0; a < size; a++) M[a + b * size] /= len;
	}
	}
	if( (binvecs = fopen(binvecs_fname, "wb")) != NULL && (binwords = fopen(binwords_fname, "wb")) != NULL) {
	fwrite(M, sizeof(float), (long long)words * (long long)size, binvecs);
	fclose(binvecs);
	fwrite(vocab, sizeof(char), (long long)words * max_w, binwords);
	fclose(binwords);
	}
	}
	if( (binvecs_fd = open(binvecs_fname, O_RDONLY)) >= 0 && (binwords_fd = open(binwords_fname, O_RDONLY)) >= 0) {
	M = mmap(0, sizeof(float) * (long long)words * (long long)size, PROT_READ, MAP_SHARED, binvecs_fd, 0);
	vocab = mmap(0, sizeof(char) * (long long)words * max_w, PROT_READ, MAP_SHARED, binwords_fd, 0);
	if (M == MAP_FAILED \|\| vocab == MAP_FAILED) {
	close(binvecs_fd);
	close(binwords_fd);
	fprintf(stderr, "Cannot mmap %s or %s\n", binwords_fname, binvecs_fname);
	exit(-1);
	}
	} else {
	fprintf(stderr, "Cannot open %s or %s\n", binwords_fname, binvecs_fname);
	exit(-1);
	}
	fclose(f);

	if(net_name && strlen(net_name) > 0) {
	if( (net_fd = open(net_name, O_RDONLY)) >= 0) {
	window = (lseek(net_fd, 0, SEEK_END) - sizeof(float) * words * size) / words / size / sizeof(float) / 2;
	// lseek(net_fd, sizeof(float) * words * size, SEEK_SET);
	// munmap(M, sizeof(float) * words * size);
	M2 = mmap(0, sizeof(float) * words * size + sizeof(float) * 2 * window * size * words, PROT_READ, MAP_SHARED, net_fd, 0);
	if (M2 == MAP_FAILED) {
	close(net_fd);
	fprintf(stderr, "Cannot mmap %s\n", net_name);
	exit(-1);
	}
	syn1neg_window = M2 + words * size;
	} else {
	fprintf(stderr, "Cannot open %s\n", net_name);
	exit(-1);
	}
	fprintf(stderr, "Successfully memmaped %s. Determined window size: %d\n", net_name, window);
	}

	expTable = (float ) malloc((EXP_TABLE_SIZE + 1) sizeof(float));
	for (i = 0; i < EXP_TABLE_SIZE; i++) {
	expTable[i] = exp((i / (float) EXP_TABLE_SIZE * 2 - 1) * MAX_EXP); // Precompute the exp() table
	expTable[i] = expTable[i] / (expTable[i] + 1); // Precompute f(x) = x / (x + 1)
	}
	return 0;
	}

	long mergeVectors(char *file_name){
	FILE f, binvecs, *binwords;
	int binwords_fd, binvecs_fd, net_fd, i;
	long long a, b, c, d, cn;
	float len;
	float *merge_vecs;
	char *merge_vocab;
	/* long long merge_words, merge_size; */
	long long merge_size;

	char binvecs_fname[256], binwords_fname[256];
	strcpy(binwords_fname, file_name);
	strcat(binwords_fname, ".words");
	strcpy(binvecs_fname, file_name);
	strcat(binvecs_fname, ".vecs");

	f = fopen(file_name, "rb");
	if (f == NULL) {
	printf("Input file %s not found\n", file_name);
	exit -1;
	}
	fscanf(f, "%lld", &merge_words);
	fscanf(f, "%lld", &merge_size);
	if(merge_size != size){
	fprintf(stderr, "vectors must have the same length\n");
	exit(-1);
	}
	if( (binvecs_fd = open(binvecs_fname, O_RDONLY)) >= 0 && (binwords_fd = open(binwords_fname, O_RDONLY)) >= 0) {
	merge_vecs = malloc(sizeof(float) * (words + merge_words) * size);
	merge_vocab = malloc(sizeof(char) * (words + merge_words) * max_w);
	if (merge_vecs == NULL \|\| merge_vocab == NULL) {
	close(binvecs_fd);
	close(binwords_fd);
	fprintf(stderr, "Cannot reserve memory for %s or %s\n", binwords_fname, binvecs_fname);
	exit(-1);
	}
	read(binvecs_fd, merge_vecs, merge_words * size * sizeof(float));
	read(binwords_fd, merge_vocab, merge_words * max_w);
	} else {
	fprintf(stderr, "Cannot open %s or %s\n", binwords_fname, binvecs_fname);
	exit(-1);
	}
	printf("Successfully reallocated memory\nMerging...\n");
	fflush(stdout);
	memcpy(merge_vecs + merge_words * size, M, words * size * sizeof(float));
	memcpy(merge_vocab + merge_words * max_w, vocab, words * max_w);
	munmap(M, words * size * sizeof(float));
	munmap(vocab, words * max_w);
	M = merge_vecs;
	vocab = merge_vocab;
	merged_end = merge_words;
	words += merge_words;
	fclose(f);
	printf("merged_end: %lld, words: %lld\n", merged_end, words);
	return((long) merged_end);
	}

	void filter_garbage() {
	long i;
	unsigned char *w, previous, c;
	garbage = malloc(words);
	memset(garbage, 0, words);
	for (i = 0; i < words; i++) {
	w = vocab + i * max_w;
	previous = 0;
	while((c = *w++) && !garbage[i]) {
	if( ((c <= 90 && c >= 65) && (previous >= 97 && previous <= 122)) \|\|
	(previous == '-' && (c & 32)) \|\|
	(previous == 0xc2 && (c == 0xa4 \|\| c == 0xb6 ))
	) {
	garbage[i]=1;
	continue;
	}
	previous = c;
	}
	}
	return;
	}

	void getCollocators(knnpars pars) {
	int N = pars->N;
	int cc = pars->wl->wordi[0];
	knn *nbs = NULL;
	long window_layer_size = size * window * 2;
	long a, b, c, d, e, window_offset, target, max_target=0, maxmax_target;
	float f, max_f, maxmax_f;
	float target_sums, bestf, *bestn, worstbest, wpos_sum;
	long long besti, bestp;

	if(M2 == NULL \|\| cc == -1)
	return NULL;

	a = posix_memalign((void *) &target_sums, 128, words sizeof(float));
	besti = malloc(N * sizeof(long long));
	bestp = malloc(N * sizeof(long long));
	bestf = malloc(N * sizeof(float));
	bestn = malloc(N * sizeof(float));

	worstbest = MIN_RESP;

	for (b = 0; b < words; b++)
	target_sums[b]=0;
	for (b = 0; b < N; b++) {
	besti[b] = -1;
	bestn[b] = 1;
	bestf[b] = worstbest;
	}

	d = cc;
	maxmax_f = -1;
	maxmax_target = 0;

	for (a = pars->from; a < pars->upto; a++) {
	if(a >= window)
	a++;
	wpos_sum = 0;
	printf("window pos: %ld\n", a);
	if (a != window) {
	max_f = -1;
	window_offset = a * size;
	if (a > window)
	window_offset -= size;
	for(target = 0; target < words; target ++) {
	if(target == d)
	continue;
	f = 0;
	for (c = 0; c < size; c++)
	f += M2[d* size + c] * syn1neg_window[target * window_layer_size + window_offset + c];
	if (f < -MAX_EXP)
	continue;
	else if (f > MAX_EXP)
	continue;
	else
	f = expTable[(int) ((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];
	wpos_sum += f;

	target_sums[target] += f;
	if(f > worstbest) {
	for (b = 0; b < N; b++) {
	if (f > bestf[b]) {
	memmove(bestf + b + 1, bestf + b, (N - b -1) * sizeof(float));
	memmove(besti + b + 1, besti + b, (N - b -1) * sizeof(long long));
	memmove(bestp + b + 1, bestp + b, (N - b -1) * sizeof(long long));
	bestf[b] = f;
	besti[b] = target;
	bestp[b] = window-a;
	break;
	}
	}
	if(b == N - 1)
	worstbest = bestf[N-1];
	}
	}
	printf("%d %.2f\n", max_target, max_f);
	printf("%s (%.2f) ", &vocab[max_target * max_w], max_f);
	if(max_f > maxmax_f) {
	maxmax_f = max_f;
	maxmax_target = max_target;
	}
	for (b = 0; b < N; b++)
	if(bestp[b] == window-a)
	bestn[b] = bestf[b] / wpos_sum;
	} else {
	printf("\x1b[1m%s\x1b[0m ", &vocab[d*max_w]);
	}

	}
	for (b = 0; b < words; b++)
	pars->target_sums[b] += (target_sums[b] / wpos_sum ) / (window * 2);
	free(target_sums);
	for(b=0; b<N && besti[b] >= 0; b++) // THIS LOOP IS NEEDED (b...)
	printf("%s %.2f %d * ", &vocab[besti[b]*max_w], bestf[b], bestp[b]);
	printf("\n");
	nbs = malloc(sizeof(knn));
	nbs->index = besti;
	nbs->dist = bestf;
	nbs->norm = bestn;
	nbs->pos = bestp;
	nbs->length = b-1;
	pthread_exit(nbs);
	}

	wordlist getTargetWords(char st1, int search_backw) {
	wordlist *wl = malloc(sizeof(wordlist));
	char st[100][max_size], sep[100];
	long a, b=0, c=0, cn=0;
	int unmerged;

	while (1) {
	st[cn][b] = st1[c];
	b++;
	c++;
	st[cn][b] = 0;
	if (st1[c] == 0) break;
	if (st1[c] == ' ' \|\| st1[c] == '-') {
	sep[cn++] = st1[c];
	b = 0;
	c++;
	}
	}
	cn++;
	for (a = 0; a < cn; a++) {
	if(search_backw) {
	for (b = words - 1; b >= 0; b--) if (!strcmp(&vocab[b * max_w], st[a])) break;
	} else {
	for (b = 0; b < words; b++) if (!strcmp(&vocab[b * max_w], st[a])) break;
	}
	if (b == words) b = -1;
	wl->wordi[a] = b;
	fprintf(stderr, "Word: \"%s\" Position in vocabulary: %lld\n", st[a], wl->wordi[a]);
	if (b == -1) {
	fprintf(stderr, "Out of dictionary word!\n");
	cn--;
	break;
	}
	}
	wl->length=cn;
	return(wl);
	}

	void _get_neighbours(knnpars pars) {
	char *st1 = pars->token;
	int N = pars->N;
	long from = pars -> from;
	unsigned long upto = pars -> upto;
	char file_name[max_size], st[100][max_size], *sep;
	float dist, len, *bestd, vec[max_size];
	long long a, b, c, d, cn, bi, besti;
	char ch;
	knn *nbs = NULL;
	wordlist *wl = pars->wl;

	besti = malloc(N * sizeof(long long));
	bestd = malloc(N * sizeof(float));

	float worstbest=-1;

	for (a = 0; a < N; a++) bestd[a] = 0;
	a = 0;
	bi = wl->wordi;
	cn = wl->length;
	sep = wl->sep;
	b = bi[0];
	c = 0;
	if (b == -1) {
	N = 0;
	goto end;
	}
	for (a = 0; a < size; a++) vec[a] = 0;
	for (b = 0; b < cn; b++) {
	if (bi[b] == -1) continue;
	if(b>0 && sep[b-1] == '-')
	for (a = 0; a < size; a++) vec[a] -= M[a + bi[b] * size];
	else
	for (a = 0; a < size; a++) vec[a] += M[a + bi[b] * size];
	}
	len = 0;
	for (a = 0; a < size; a++) len += vec[a] * vec[a];
	len = sqrt(len);
	for (a = 0; a < size; a++) vec[a] /= len;
	for (a = 0; a < N; a++) bestd[a] = -1;
	for (c = from; c < upto; c++) {
	if(garbage && garbage[c]) continue;
	a = 0;
	// do not skip taget word
	// for (b = 0; b < cn; b++) if (bi[b] == c) a = 1;
	// if (a == 1) continue;
	dist = 0;
	for (a = 0; a < size; a++) dist += vec[a] * M[a + c * size];
	if(dist > worstbest) {
	for (a = 0; a < N; a++) {
	if (dist > bestd[a]) {
	memmove(bestd + a + 1, bestd + a, (N - a -1) * sizeof(float));
	memmove(besti + a + 1, besti + a, (N - a -1) * sizeof(long long));
	bestd[a] = dist;
	besti[a] = c;
	break;
	}
	}
	worstbest = bestd[N-1];
	}
	}

	nbs = malloc(sizeof(knn));
	nbs->index = besti;
	nbs->dist = bestd;
	nbs->length = N;
	end:
	pthread_exit(nbs);
	}


	SV get_neighbours(char st1, int N, int sort_by, int search_backw) {
	HV *result = newHV();
	float *target_sums, bestd[MAX_NEIGHBOURS], bestn[MAX_NEIGHBOURS], bests[MAX_NEIGHBOURS], vec[max_size];
	long long old_words;
	long besti[MAX_NEIGHBOURS], bestp[MAX_NEIGHBOURS], a, b, c, d, slice;
	knn *para_nbs[MAX_THREADS];
	knn *syn_nbs[MAX_THREADS];
	knnpars pars[MAX_THREADS];
	pthread_t pt = (pthread_t )malloc((num_threads+1) * sizeof(pthread_t));
	wordlist *wl;
	int syn_threads = (M2? window * 2 : 0);
	int para_threads = num_threads - syn_threads;

	if(N>MAX_NEIGHBOURS) N=MAX_NEIGHBOURS;


	wl = getTargetWords(st1, search_backw);
	if(wl->length < 1)
	goto end;

	old_words = words;
	if(merge_words > 0)
	words = merge_words * 1.25; /* HACK */
	slice = words / para_threads;

	a = posix_memalign((void *) &target_sums, 128, words sizeof(float));
	for(a = 0; a < words; a++)
	target_sums[a] = 0;

	printf("Starting %d threads\n", para_threads);
	fflush(stdout);
	for(a=0; a < para_threads; a++) {
	pars[a].token = st1;
	pars[a].wl = wl;
	pars[a].N = N;
	pars[a].from = a*slice;
	pars[a].upto = ((a+1)slice > words? words:(a+1)slice);
	pthread_create(&pt[a], NULL, _get_neighbours, (void *) &pars[a]);
	}
	if(M2) {
	for(a=0; a < syn_threads; a++) {
	pars[a + para_threads].target_sums = target_sums;
	pars[a + para_threads].wl = wl;
	pars[a + para_threads].N = N;
	pars[a + para_threads].from = a;
	pars[a + para_threads].upto = a+1;
	pthread_create(&pt[a + para_threads], NULL, getCollocators, (void *) &pars[a + para_threads]);
	}
	}
	printf("Waiting for para threads to join\n");
	fflush(stdout);
	for (a = 0; a < para_threads; a++) pthread_join(pt[a], &para_nbs[a]);
	printf("Para threads joint\n");
	fflush(stdout);

	/* if(!syn_nbs[0]) */
	/* goto end; */

	for(b=0; b < N; b++) {
	besti[b] = para_nbs[0]->index[b];
	bestd[b] = para_nbs[0]->dist[b];
	}

	for(a=1; a < para_threads; a++) {
	for(b=0; b < para_nbs[a]->length && para_nbs[a]->index[b] >= 0; b++) {
	for(c=0; c < N * para_threads; c++) {
	if(para_nbs[a]->dist[b] > bestd[c]) {
	for(d=N-1; d>c; d--) {
	bestd[d] = bestd[d-1];
	besti[d] = besti[d-1];
	}
	besti[c] = para_nbs[a]->index[b];
	bestd[c] = para_nbs[a]->dist[b];
	break;
	}
	}
	}
	}

	AV* array = newAV();
	int i;
	int l1_words=0, l2_words=0;
	for (a = 0, i = 0; i < N && a < 600; a++) {
	long long c = besti[a];
	if(merge_words > 0) {
	if(c >= merge_words) {
	if(l1_words > N / 2)
	continue;
	else
	l1_words++;
	} else {
	if(l2_words > N / 2)
	continue;
	else
	l2_words++;
	}
	}
	fflush(stdout);
	printf("%s l1:%d l2:%d i:%d a:%ld\n", &vocab[c * max_w], l1_words, l2_words, i, a);

	HV* hash = newHV();
	SV* word = newSVpvf(&vocab[c * max_w], 0);
	if(latin_enc == 0) SvUTF8_on(word);
	fflush(stdout);
	hv_store(hash, "word", strlen("word"), word , 0);
	hv_store(hash, "dist", strlen("dist"), newSVnv(bestd[a]), 0);
	hv_store(hash, "rank", strlen("rank"), newSVuv(besti[a]), 0);
	AV *vector = newAV();
	for (b = 0; b < size; b++) {
	av_push(vector, newSVnv(M[b + besti[a] * size]));
	}
	hv_store(hash, "vector", strlen("vector"), newRV_noinc((SV*)vector), 0);
	av_push(array, newRV_noinc((SV*)hash));
	i++;
	}
	hv_store(result, "paradigmatic", strlen("paradigmatic"), newRV_noinc((SV*)array), 0);

	for(b=0; b < MAX_NEIGHBOURS; b++) {
	besti[b] = -1L;
	bestd[b] = 0;
	bestn[b] = 0;
	bestp[b] = 0;
	bests[b] = 0;
	}

	if (M2) {
	printf("Waiting for syn threads to join\n");
	fflush(stdout);
	for (a = 0; a < syn_threads; a++) pthread_join(pt[a+para_threads], &syn_nbs[a]);
	printf("syn threads joint\n");
	fflush(stdout);

	for(b=0; b < syn_nbs[0]->length; b++) {
	besti[b] = syn_nbs[0]->index[b];
	bestd[b] = syn_nbs[0]->dist[b];
	bestn[b] = syn_nbs[0]->norm[b];
	bestp[b] = syn_nbs[0]->pos[b];
	bests[b] = target_sums[syn_nbs[0]->index[b]];
	}

	if(sort_by != 1) { // sort by responsiveness
	for(a=1; a < syn_threads; a++) {
	for(b=0; b < syn_nbs[a]->length; b++) {
	for(c=0; c < MAX_NEIGHBOURS; c++) {
	if(syn_nbs[a]->dist[b] > bestd[c]) {
	for(d=MAX_NEIGHBOURS-1; d>c; d--) {
	bestd[d] = bestd[d-1];
	besti[d] = besti[d-1];
	bestn[d] = bestn[d-1];
	bestp[d] = bestp[d-1];
	}
	besti[c] = syn_nbs[a]->index[b];
	bestd[c] = syn_nbs[a]->dist[b];
	bestn[c] = syn_nbs[a]->norm[b];
	bestp[c] = syn_nbs[a]->pos[b];
	break;
	}
	}
	}
	}
	} else { // sort by mean p
	for(a=1; a < syn_threads; a++) {
	for(b=0; b < syn_nbs[a]->length; b++) {
	for(c=0; c < MAX_NEIGHBOURS; c++) {
	if(target_sums[syn_nbs[a]->index[b]] > bests[c]) {
	for(d=MAX_NEIGHBOURS-1; d>c; d--) {
	bestd[d] = bestd[d-1];
	besti[d] = besti[d-1];
	bestn[d] = bestn[d-1];
	bestp[d] = bestp[d-1];
	bests[d] = bests[d-1];
	}
	besti[c] = syn_nbs[a]->index[b];
	bestd[c] = syn_nbs[a]->dist[b];
	bestn[c] = syn_nbs[a]->norm[b];
	bestp[c] = syn_nbs[a]->pos[b];
	bests[c] = target_sums[syn_nbs[a]->index[b]];
	break;
	}
	}
	}
	}
	}
	array = newAV();
	for (a = 0; a < MAX_NEIGHBOURS && besti[a] >= 0; a++) {
	HV* hash = newHV();
	SV* word = newSVpvf(&vocab[besti[a] * max_w], 0);
	if(latin_enc == 0) SvUTF8_on(word);
	hv_store(hash, "word", strlen("word"), word , 0);
	hv_store(hash, "dist", strlen("dist"), newSVnv(bestd[a]), 0);
	hv_store(hash, "norm", strlen("norm"), newSVnv(bestn[a]), 0);
	hv_store(hash, "sum", strlen("sum"), newSVnv(target_sums[besti[a]]), 0);
	hv_store(hash, "pos", strlen("pos"), newSVnv(bestp[a]), 0);
	av_push(array, newRV_noinc((SV*)hash));
	}
	hv_store(result, "syntagmatic", strlen("syntagmatic"), newRV_noinc((SV*)array), 0);
	}
	end:
	words = old_words;
	return newRV_noinc((SV*)result);
	}

	int dump_vecs(char *fname) {
	long i, j;
	FILE *f;
	/* if(words>200000) */
	/* words=200000; */

	if((f=fopen(fname, "w")) == NULL) {
	fprintf(stderr, "cannot open %s for writing\n", fname);
	return(-1);
	}
	fprintf(f, "%lld %lld\n", words, size);
	for (i=0; i < words; i++) {
	fprintf(f, "%s ", &vocab[i * max_w]);
	for(j=0; j < size - 1; j++)
	fprintf(f, "%f ", M[i*size + j]);
	fprintf(f, "%f\n", M[i*size + j]);
	}
	fclose(f);
	return(0);
	}