Как скомпилировать этот код c++ в WebAssembly (или почему вывод wasm-файла отличается от вывода c++ программы)?

Question

[Magneto903]

У меня относительно несложная c++ программа, которая выполняет модифицированный алгоритм Дейкстры с очередью (вершина в очереди может оказаться несколько раз).
https://www.onlinegdb.com/yutiVBNOf
Но я писал эту программу, чтобы ускорить процесс в веб приложении, поэтому я хотел скомпилировать её в WASM-модуль, чтобы потом вызывать из JavaScript'а
Однако, когда я запускаю этот WASM-модуль, он выдает мне не то, что выдавала исходная c++ программа (на тех же входных данных), а совершенно другие (некорректные) данные.

Я тестировал и собирал WASM-модуль при помощи этого сервиса

с++ код, который я пытался скомпилировать в wasm-модуль (левое окно сервиса)

#include <iostream>

using namespace std;


int v[1000];
float cache_1[1000];
int cache_2[1000];
int s[5000];
int e[5000];
float l[5000];
int graph_1[1000][20];
float graph_2[1000][20];

float queue_1[1000];
int queue_2[1000];
int queue_ids[1000];

int links_1[1000][20];
float links_2[1000][20];


void init_arr() {
  for (int i=0; i < 1000; ++i) {
    v[i] = -2;
    cache_1[i] = -2.0;
    cache_2[i] = -2;
  }
  for (int i=0; i < 5000; i++) {
    s[i] = -2;
    e[i] = -2;
    l[i] = -2.0;
  }
  for (int i=0; i < 1000; i++) {
    for (int j=0; j < 20; j++) {
      graph_1[i][j] = -2;
      graph_2[i][j] = -2.0;
    }
  }
}

void add_point(int i, int point) {
  v[i] = point;
}

void add_edge(int i, int s_p, int e_p, float edge_len) {
  s[i] = s_p;
  e[i] = e_p;
  l[i] = edge_len;
}

void fill_graph() {
  for (int i=0; i < 5000; i++) {
    int start = s[i];
    int end = e[i];
    float dist = l[i];
    if (start == -2) {
      break;
    }
    // найдём место, куда вставить
    int j = 0;
    while (graph_1[start][j] > -2) {
      j++;
    }
    graph_1[start][j] = end;
    graph_2[start][j] = dist;
    j=0;
    while (graph_1[end][j] > -2) {
      j++;
    }
    graph_1[end][j] = start;
    graph_2[end][j] = dist;
  }
}

void get_dists(int a) {
  
  int L=0;
  for (int i=0; i<1000; i++) {
    if (graph_1[i][0] > -2) {
      L++;
    } else {
      break;
    }
  }
  
  for (int i=0; i < 1000; i++) {
    for (int j=0; j < 20; j++) {
      links_1[i][j] = -2;
      links_2[i][j] = -2.0;
    }
  }
  
  int i = L;
  
  while (--i >= 0) {
    
    cache_1[i] = 100000.0;
    cache_2[i] = i;
    for (int j=0; j < 20; j++) {
      
      links_1[i][j] = graph_1[i][j];
      links_2[i][j] = graph_2[i][j];
    }
  }
  
  
  float root_1 = cache_1[a];
  int root_2 = cache_2[a];
  
  cache_1[a] = 0;
  cache_2[a] = -1;
  

  root_1 = 0.0;
  root_2 = -1;
  
  
  
  for (int j=0; j < 1000; j++) {
    queue_1[j] = -2.0;
    queue_ids[j] = -2;
  }
  
  queue_1[0] = root_1;
  queue_ids[0] = 0;
  
  i=0;
  int len = 1;
  
  
  while (i < len) {
    float node_1 = queue_1[i];
    int node_id = queue_ids[i];
    
    int node_verts_len = 0;
    
    for (int j=0; j < 20; j++) {
      if (links_1[node_id][j] > -2) {
        node_verts_len++;
      }
    }
    
    int j = node_verts_len-1;
    while (j >= 0) {
      
      int link_vert = links_1[node_id][j];
      float link_dist = links_2[node_id][j];

      float c1 = cache_1[link_vert];
      int c2 = cache_2[link_vert];
      
      float d = node_1 + link_dist;
      
      if (d < c1) {
        cache_1[link_vert] = d;
        cache_2[link_vert] = node_id;
        
        queue_1[len] = d;
        queue_ids[len] = link_vert;
        len+=1;
      }
      j--;
    }
    i++;
  }
}


float get_cache_1(int i) {
  return cache_1[i];
}

int get_cache_2(int i) {
  return cache_2[i];
}



int main() {
    
    init_arr();
    
    add_point(0, 0);
    add_point(1, 1);
    add_point(2, 2);
    add_point(3, 3);
    add_point(4, 4);
    
    add_edge(0, 0, 2, 1);
    add_edge(1, 0, 1, 1);
    add_edge(2, 1, 2, 1);
    add_edge(3, 2, 3, 1);
    add_edge(4, 2, 4, 1);
    add_edge(5, 3, 4, 1);
    
    fill_graph();
    
    get_dists(0);
    
    
    for (int i=0; i < 5; i++) {
        //cout << i << " " << get_cache_1(i) << " " << get_cache_2(i) << endl;
    }
    
  return 0;
}

JS-код, который вызывает wasm-модуль (правое окно сервиса)

var wasmModule = new WebAssembly.Module(wasmCode);
var wasmInstance = new WebAssembly.Instance(wasmModule, wasmImports);
var wasm_module = wasmInstance.exports

wasm_module.main();

for (var i=0; i < 5; i++) {
  var c1 = wasm_module['_Z11get_cache_1i'](i);
  var c2 = wasm_module['_Z11get_cache_2i'](i);
  
  log(i+" " +c1 + " " + c2)
}

Как мне всё-таки добиться, чтобы wasm-модуль работал правильно?
Сейчас он выдает:

0 0 -1
1 100000 1
2 100000 2
3 100000 3
4 100000 4

А должен выдавать это:

0 0 -1                                                                                                                                        
1 1 0                                                                                                                                         
2 1 0                                                                                                                                         
3 2 2                                                                                                                                         
4 2 2

Comments

[Армянское Радио]

В этой мешанине однобуквенных глобальных переменных разобраться нереально, наверняка вы где-то что-то напутали, что привело к UB

Как починить - привести код в порядок - нормально назвать сущности, убрать глобальные переменные.

[Magneto903]

Фокс Йовович, а как wasm-модуль вообще мог собраться, если у меня UB?

[Армянское Радио]

Magneto903, а UB на компилируемость программы никак не влияет, на то оно и UB.

[Magneto903]

Фокс Йовович, на винде есть возможность отловить все UB?

[Армянское Радио]

Magneto903, нет, это можно сделать только внимательным анализом кода или разными статическими анализаторами

[Magneto903]

Фокс Йовович, боюсь без глобальных переменных я не смогу передавать данные между wasm-модулем и javascript'ом

[Армянское Радио]

Magneto903, Ха, чтобы передавать значения между модулем и скриптом, нужно применить определенное колдунство, иначе будет мусор вместо данных.

https://emscripten.org/docs/porting/connecting_cpp...

[Magneto903]

Фокс Йовович, Вы что, хотите сказать, что я не могу передавать просто числа, а уже в самом c++ модуле, собирать эти числа в массивы и более сложные структуры? И потом просто по индексу извлекать каждый элемент из этих сложных структур?

[Армянское Радио]

Magneto903, вы должны выделять память вот тем способом, что приведен в документации. Вы можете выделить массив под js, вызвав malloc и передать его адрес в программу на C++. Этот способ точно работает, я проверял (и не только я)

[Magneto903]

Фокс Йовович, ну а доставать данные то как? Или массив, который я передам будет обновляться во время выполнения c++?

[Magneto903]

Фокс Йовович, а чтобы пустой массив инициализировать, я тоже должен передать пустой массив через js? А если он двумерный?

[Армянское Радио]

Magneto903, В мануале написано, что массив можно передавать в обе стороны (И это точно работает).
Двумерный массив всегда можно представить как одномерный, при помощи фокуса a[i][j] = o[i*width+j]

[none7]

А, что там за memcpy null ? Судя по всему memcpy не компилируется в wasm, а импортируется. Но у меня есть сомнения, что эта функция есть в wasmimports.

Answer 1

[none7]

Действительно проблема в WasmFiddle. Он генерирует код, который нуждается в функции memcpy(импорт), но не реализует её в импорте. Добавил простенькую функцию:

void* memcpy(char* dst, char* src, int count) {
  while(count--) *dst++ = *src++;
}

И чуть изменил JS-код

var wasmModule = new WebAssembly.Module(wasmCode);
var wasmInstance = new WebAssembly.Instance(wasmModule, wasmImports);
var wasm_module = wasmInstance.exports

wasm_module.main();

for (var i=0; i < 5; i++) {
  var c1 = wasm_module.get_cache_1(i);
  var c2 = wasm_module.get_cache_2(i);
  
  log(i+" " +c1 + " " + c2);
}

Выводит в точности то, что Вы ожидаете.

Comments

[Magneto903]

none7 , а куда именно вы добавили функцию memcpy? В c++ код? А в какое место c++ кода? Просто я добавил в самое начало. Однако у меня теперь в консоли ошибка

Uncaught DOMException: Failed to execute 'atob' on 'Window': The string to be decoded is not correctly encoded.

C++ код, который я вписал в левое окно

#include <iostream>

using namespace std;


int v[1000];
float cache_1[1000];
int cache_2[1000];
int s[5000];
int e[5000];
float l[5000];
int graph_1[1000][20];
float graph_2[1000][20];

float queue_1[1000];
int queue_2[1000];
int queue_ids[1000];

int links_1[1000][20];
float links_2[1000][20];

void* memcpy(char* dst, char* src, int count) {
  while(count--) *dst++ = *src++;
}



void init_arr() {
  for (int i=0; i < 1000; ++i) {
    v[i] = -2;
    cache_1[i] = -2.0;
    cache_2[i] = -2;
  }
  for (int i=0; i < 5000; i++) {
    s[i] = -2;
    e[i] = -2;
    l[i] = -2.0;
  }
  for (int i=0; i < 1000; i++) {
    for (int j=0; j < 20; j++) {
      graph_1[i][j] = -2;
      graph_2[i][j] = -2.0;
    }
  }
}

void add_point(int i, int point) {
  v[i] = point;
}

void add_edge(int i, int s_p, int e_p, float edge_len) {
  s[i] = s_p;
  e[i] = e_p;
  l[i] = edge_len;
}

void fill_graph() {
  for (int i=0; i < 5000; i++) {
    int start = s[i];
    int end = e[i];
    float dist = l[i];
    if (start == -2) {
      break;
    }
    // найдём место, куда вставить
    int j = 0;
    while (graph_1[start][j] > -2) {
      j++;
    }
    graph_1[start][j] = end;
    graph_2[start][j] = dist;
    j=0;
    while (graph_1[end][j] > -2) {
      j++;
    }
    graph_1[end][j] = start;
    graph_2[end][j] = dist;
  }
}

void get_dists(int a) {
  
  int L=0;
  for (int i=0; i<1000; i++) {
    if (graph_1[i][0] > -2) {
      L++;
    } else {
      break;
    }
  }
  
  for (int i=0; i < 1000; i++) {
    for (int j=0; j < 20; j++) {
      links_1[i][j] = -2;
      links_2[i][j] = -2.0;
    }
  }
  
  int i = L;
  
  while (--i >= 0) {
    
    cache_1[i] = 100000.0;
    cache_2[i] = i;
    for (int j=0; j < 20; j++) {
      
      links_1[i][j] = graph_1[i][j];
      links_2[i][j] = graph_2[i][j];
    }
  }
  
  
  float root_1 = cache_1[a];
  int root_2 = cache_2[a];
  
  cache_1[a] = 0;
  cache_2[a] = -1;
  

  root_1 = 0.0;
  root_2 = -1;
  
  
  
  for (int j=0; j < 1000; j++) {
    queue_1[j] = -2.0;
    queue_ids[j] = -2;
  }
  
  queue_1[0] = root_1;
  queue_ids[0] = 0;
  
  i=0;
  int len = 1;
  
  
  while (i < len) {
    float node_1 = queue_1[i];
    int node_id = queue_ids[i];
    
    int node_verts_len = 0;
    
    for (int j=0; j < 20; j++) {
      if (links_1[node_id][j] > -2) {
        node_verts_len++;
      }
    }
    
    int j = node_verts_len-1;
    while (j >= 0) {
      
      int link_vert = links_1[node_id][j];
      float link_dist = links_2[node_id][j];

      float c1 = cache_1[link_vert];
      int c2 = cache_2[link_vert];
      
      float d = node_1 + link_dist;
      
      if (d < c1) {
        cache_1[link_vert] = d;
        cache_2[link_vert] = node_id;
        
        queue_1[len] = d;
        queue_ids[len] = link_vert;
        len+=1;
      }
      j--;
    }
    i++;
  }
}


float get_cache_1(int i) {
  return cache_1[i];
}

int get_cache_2(int i) {
  return cache_2[i];
}




int main() {
    
    init_arr();
    
    add_point(0, 0);
    add_point(1, 1);
    add_point(2, 2);
    add_point(3, 3);
    add_point(4, 4);
    
    add_edge(0, 0, 2, 1);
    add_edge(1, 0, 1, 1);
    add_edge(2, 1, 2, 1);
    add_edge(3, 2, 3, 1);
    add_edge(4, 2, 4, 1);
    add_edge(5, 3, 4, 1);
    
    fill_graph();
    
    get_dists(0);
    
    
    for (int i=0; i < 5; i++) {
        //cout << i << " " << get_cache_1(i) << " " << get_cache_2(i) << endl;
    }
    
  return 0;
}

[none7]

Выкинь

#include <iostream>
using namespace std;

Этот сервис похоже не дружит с C++ кодом, только чистый Си.

[Magneto903]

none7, УРА, ЗАРАБОТАЛО!!! Спасибо Вам огромное! Я уже несколько дней с этой проблемой разбирался, и только Вы смогли помочь!

[none7]

Magneto903, А нет, просто я в сервисе не разобрался и компилировал как Си. Но странно, у меня с С++14 всё работает и с этими строками без ошибок.

[Magneto903]

none7, я использовал c++ 98, видимо его нельзя использовать

[Magneto903]

none7, Можете пожалуйста помочь?
Тот код плохо работал, поэтому я его аккуратно переписал
Всё значит работает, хорошо
Перехожу на тот самый сервис WasmFiddle

в левое окно я вставил это

int edges_start[3000];
int edges_end[3000];
float edges_len[3000];

int g_links_id[1000][100];
float g_links_weight[1000][100];

int cache_id[1000];
float cache_distance[1000];
int cache_prev[1000];
int cache_links_id[1000][100];
float cache_links_weight[1000][100];

int queue_id[1000];
float queue_distance[1000];
int queue_prev[1000];
int queue_links_id[1000][100];
float queue_links_weight[1000][100];

void* memcpy(char* dst, char* src, int count) {
  while(count--) *dst++ = *src++;
}


void init_cpp() {
	for (int i=0; i < 1000; i++) {
		cache_id[i] = -2;
		queue_id[i] = -2;
		cache_distance[i] =  100000;
		queue_distance[i] = 100000;
		cache_prev[i] = -2;
		queue_prev[i] = -2;
		for (int j=0; j < 100; j++) {
			queue_links_id[i][j] = -2;
			queue_links_weight[i][j] = 100000;
			cache_links_id[i][j] = -2;
			cache_links_weight[i][j] = 100000;
		}
	}
}

void init_edges_cpp() {
	for (int i=0; i < 3000; i++) {
		edges_start[i] = -2;
		edges_end[i] = -2;
		edges_len[i] = -2.0;
	}

	for (int i=0; i < 1000; i++) {
		for (int j=0; j < 100; j++) {
			g_links_id[i][j] = -2;
			g_links_weight[i][j] = -2.0;
		}
	}
}

void add_edge_cpp(int index, int start, int end, float len) {
	edges_start[index] = start;
	edges_end[index] = end;
	edges_len[index] = len;
}

void fill_graph_cpp() {
	for (int i=0; i < 3000; i++) {
		int s = edges_start[i];
		int e = edges_end[i];
		float len = edges_len[i];

		if (s == -2) {
			break;
		}

		//console.log(s, e, len)

		//var links_len = get_len(g_links_id[s])
		int links_len = 0;

		for (int j=0; j < 100; j++) {
			if (g_links_id[s][j] == -2) {
				links_len = j;
				break;
			}
		}
		//console.log(g_links_id)
		g_links_id[s][links_len] = e;
		g_links_weight[s][links_len] = len;
		//console.log(get_len(g_links_id[s]))

		//var links_len = get_len(g_links_id[e])
		for (int j=0; j < 100; j++) {
			if (g_links_id[e][j] == -2) {
				links_len = j;
				break;
			}
		}
		g_links_id[e][links_len] = s;
		g_links_weight[e][links_len] = len;
	}
}


void get_dists_cpp(int a, int L) {
	
    
    // initialization

    //int L=1000
    
    /*
    console.log('new cache: ')
    console.log(cache_links_id)
    console.log(cache_links_weight)
    */

    int i = L;
    while (--i >= 0) {
    	
        //v_links_id = g_links_id[i];
        //v_links_weight = g_links_weight[i];
        //cache_distance[i] = 100000;
        //cache_prev[i] = -2;
        
        for (int j = 0; j < 100; j++) {
        	//console.log()
        	if (g_links_id[i][j] == -2) {
        	    break;
        	}
        	cache_links_id[i][j] = g_links_id[i][j];
        	cache_links_weight[i][j] = g_links_weight[i][j];
        }
        //console.log(v.links)
        //console.log(cache_links_id[i])
        //console.log(cache_links_weight[i])
        cache_id[i] = i;
    }


    queue_id[0] = cache_id[a];
    cache_distance[a] = 0;
    queue_distance[0] = cache_distance[a];
    queue_prev[0] = queue_prev[a];
    for (int j=0; j < 100; j++) {
    	queue_links_id[0][j] = cache_links_id[a][j];
    	queue_links_weight[0][j] = cache_links_weight[a][j];
    }
    
  
    
    i=0;
    int queue_len = 1;
    while (i < queue_len) {
    	int node_id = queue_id[i];
    	float node_distance = queue_distance[i];
    	int node_prev = queue_prev[i];

    	//links_id = queue_links_id[i]
    	//links_weight = queue_links_weight[i]

    	//j = get_len(links_id)
    	int j=0;
    	for (int k=0; k < 100; k++) {
    		if (queue_links_id[i][k] == -2) {
    			j=k;
    			break;
    		}
    	}

    	while (--j >= 0) {
    		int link_id = queue_links_id[i][j];
    		float link_weight = queue_links_weight[i][j];

    		int c_id = cache_id[link_id];
    		float c_distance = cache_distance[link_id];
    		int c_prev = cache_prev[link_id];

    		float d = node_distance + link_weight;
    		if (d < c_distance) {
    			cache_prev[link_id] = node_id;
    			cache_distance[link_id] = d;
    			//last_ind = get_len(queue_id)
    			/*
    			for (var k=0; k < 1000; k++) {
    				if (queue_id[k] == undefined) {
    					last_ind = k;
    					break;
    				}
    			}*/
    			int last_ind = queue_len;
    			queue_id[last_ind] = cache_id[link_id];
    			queue_distance[last_ind] = cache_distance[link_id];
    			//console.log(last_ind, queue_links_id[last_ind])
    			for (int k=0; k < 100; k++) {
    				if (cache_links_id[link_id][k] == -2) {
    					break;
    				}
    				
			    	queue_links_id[last_ind][k] = cache_links_id[link_id][k];
			    	queue_links_weight[last_ind][k] = cache_links_weight[link_id][k];
			    }
			    queue_prev[last_ind] = cache_prev[link_id];
			    queue_len++;
    		}

    	}
    	i++;
    }

}

float get_cache_distance(int index) {
    return cache_distance[index];
}

int get_cache_prev(int index) {
    return cache_prev[index];
}



int main() {
    init_edges_cpp();
    init_cpp();
    add_edge_cpp(0, 0, 2, 1);
    add_edge_cpp(1, 0, 1, 1);
    add_edge_cpp(2, 1, 2, 1);
    add_edge_cpp(3, 2, 3, 1);
    add_edge_cpp(4, 2, 4, 1);
    add_edge_cpp(5, 3, 4, 1);
    fill_graph_cpp();
    
    get_dists_cpp(0, 10);
    /*
    for (int i=0; i < 10; i++) {
        cout << i << " " << get_cache_distance(i) << " " << get_cache_prev(i) << endl;
    }
    */
    
    return 0;
}

в правое окно это

var wasmModule = new WebAssembly.Module(wasmCode);
var wasmInstance = new WebAssembly.Instance(wasmModule, wasmImports);
var wasm_module = wasmInstance.exports;

console.log(wasm_module)

wasm_module.main();
  
for (var i=0; i < 5; i++) {
  var c_dist = wasm_module.get_cache_distance(i)
  console.log(c_dist)
}

в настройках стоит
-03 -std=C99
и в выводе я получаю:

0
100000
100000
100000
100000

Ну это неправильный вывод((

В чем может быть ошибка?

[none7]

То была сильно упрощённая функция, теперь сгенерированный код требует по крайней мере такую

void* memcpy(char* dst, char* src, int count) {
  void* p=dst;
  while(count--) *dst++ = *src++;
  return p;
}

Вообще ради производительности стоит скопипастить эту функцию из библиотеки. Например тут.

[Magneto903]

none7, Спасибо огромное!!!

[Magneto903]

none7, а насколько приблизительно пример из библиотеки ускорит работу?

[Magneto903]

none7, просто этот сервис почему-то ругается на (uintptr_t)

error: use of undeclared identifier 'uintptr_t'

[Magneto903]

Magneto903, А всё, понял. Нужно было добавить #include <stdint.h>

[none7]

Magneto903, Если честно, понятия не имею насколько этот код может ускорить. Всё зависит от того, есть ли данные в кэше процессора и насколько хорошо процессор работает с невыровоненными данными. В лучшем случае код будет быстрее в разы, в худшем, будет чуть медленнее. А уж насколько он ускорит весь код в целом это вообще невозможно вычислить без тестов. Но с оптимизациями всегда стоит надеяться на лучшее, особенно, когда результат приходит без существенных затрат времени.

[Magneto903]

none7, а могли бы вы в целом сказать, как-то можно ускорить этот код? Я добавил сохранение длины каждого подмассива в массиве queue_links_idОднако это не дало сильного преимущества в скорости.
финальный код выглядит так

[none7]

Magneto903, С оптимизацией алгоритмов это не ко мне. Могу лишь выразить сомнения в необходимости использования float.

[Magneto903]

none7, понятно... Да просто я переписывал этот алгоритм на C, чтобы потом скомпилировать в wasm и таким образом повысить производительность. Но почему-то wasm - код работает медленнее, чем нативный js.
Вот я и подумал, что с C-кодом что-то не так