🎯 수도쿠 문제를 Wasm과 자바스크립트로 각각 풀며, 성능 차이를 비교합니다.
해당 글에서는 C 코드를 wasm으로 변환하고, 변환한 코드로 연산을 수행한 후에 자바스크립트와 비교하는 과정을 담았습니다.
개요
- 수도쿠 문제를 JS와 WASM(C를 사용)으로 풀어서 연산 속도를 비교해보자
- 웹 플랫폼에서 비교를 진행하며, webWorker로 병렬적으로 각각 연산을 수행한다.
사용한 풀이법
- 수도쿠 문제(16x16)를 문자열로 받는다.
- 받은 문자열을 2차원 배열로 만든다.
- 재귀적으로 백트래킹 알고리즘을 사용하여 모든 해를 탐색한다.
- 수도쿠 보드를 완성했다면 결과를 다시 문자열로 합친 후 반환한다.
- 반환 받은 값을 브라우저에 나타낸다.
수도쿠 풀이 코드
JavaScript
import { strToTwoDArr, twoDArrToStr } from "./";
type Problem = string;
type Board = string[][];
interface IsValid {
board: Board;
r: number;
c: number;
num: string;
}
export const sudokuSolve = (problem: Problem) => {
const board = strToTwoDArr(problem);
const len = board.length;
const divider = Math.floor(Math.sqrt(len));
const numbers = Array.from({ length: len }, (_, i) => {
if (i + 1 < 10) return String(i + 1);
else return String.fromCharCode(65 + (i + 1 - 10));
});
let isFinish = false;
const solve = () => {
if (isFinish) return;
const pos = emptyPos();
if (pos.length === 0) {
isFinish = true;
return;
}
const [r, c] = pos;
for (const num of numbers) {
if (isValid({ board, r, c, num })) {
board[r][c] = num;
solve();
if (isFinish) return;
board[r][c] = "0";
}
}
};
const emptyPos = () => {
for (let r = 0; r < len; r++) {
for (let c = 0; c < len; c++) {
if (board[r][c] === "0") return [r, c];
}
}
return [];
};
const isValid = ({ r, c, num }: IsValid) => {
for (let i = 0; i < len; i++) {
if (board[r][i] === num) {
return false;
}
}
for (let i = 0; i < len; i++) {
if (board[i][c] === num) {
return false;
}
}
const startRow = Math.floor(r / divider) * divider;
const startCol = Math.floor(c / divider) * divider;
for (let i = 0; i < divider; i++) {
for (let j = 0; j < divider; j++) {
if (board[startRow + i][startCol + j] === num) {
return false;
}
}
}
return true;
};
solve();
return twoDArrToStr(board);
};C
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <string.h>
#include <emscripten/emscripten.h>
#define SIZE 16
typedef char Board[SIZE][SIZE];
EMSCRIPTEN_KEEPALIVE bool isValid(Board board, int r, int c, char num) {
int divider = sqrt(SIZE);
for (int i = 0; i < SIZE; i++) {
if (board[r][i] == num) {
return false;
}
}
for (int i = 0; i < SIZE; i++) {
if (board[i][c] == num) {
return false;
}
}
int startRow = floor(r / divider) * divider;
int startCol = floor(c / divider) * divider;
for (int i = 0; i < divider; i++) {
for (int j = 0; j < divider; j++) {
if (board[startRow + i][startCol + j] == num) {
return false;
}
}
}
return true;
}
EMSCRIPTEN_KEEPALIVE void emptyPos(Board board, int* r, int* c) {
for (*r = 0; *r < SIZE; (*r)++) {
for (*c = 0; *c < SIZE; (*c)++) {
if (board[*r][*c] == '0') return;
}
}
*r = -1;
*c = -1;
}
EMSCRIPTEN_KEEPALIVE bool solve(Board board) {
int r, c;
emptyPos(board, &r, &c);
if (r == -1) {
return true;
}
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, r, c, num)) {
board[r][c] = num;
if (solve(board)) return true;
board[r][c] = '0';
}
}
for (char num = 'A'; num <= 'G'; num++) {
if (isValid(board, r, c, num)) {
board[r][c] = num;
if (solve(board)) return true;
board[r][c] = '0';
}
}
return false;
}
EMSCRIPTEN_KEEPALIVE char* sudoku_solve(char* input){
int len = sqrt(strlen(input));
Board initialBoard;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
initialBoard[i][j] = '0';
}
}
for (int i = 0; i < strlen(input); i++) {
initialBoard[i / SIZE][i % SIZE] = input[i];
}
solve(initialBoard);
char* result = (char*)malloc((SIZE * SIZE * 3 + 1) * sizeof(char));
result[0] = '\0';
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
result[i*SIZE+j] = initialBoard[i][j];
}
}
return result;
}
int main() {
return 0;
}emsdk를 이용하여 C 모듈을 JS 파일로 컴파일하기
- emsdk를 이용하면 C 코드를 웹 환경에서 실행 가능한 JS 코드로 변환할 수 있다.
- emsdk에 대해서 잘 모르신다면 여기로
컴파일 명령어
emcc --no-entry ./sudoku_solve.c -o ./sudoku_solve.js \
-O3 \
-s ENVIRONMENT='web' \
-s EXPORTED_FUNCTIONS='["_sudoku_solve"]' \
-s EXPORT_ES6=1 \
-s EXPORTED_RUNTIME_METHODS='["cwrap"]'- —no-entry
- 메인 함수를 제외하고 모듈을 생성
- EXPORTED_FUNCTIONS
- 외부로 노출 시킬 함수를 의미한다.
- EXPORT_ES6=1
- ES6 모듈 형식으로 JS 코드를 내보내기.
- EXPORTED_RUNTIME_METHODS
- JavaScript에서 컴파일된 C 함수를 호출하기 위해 추가한 옵션
- cwrap와 ccal이 있다. ccal의 경우 C 함수를 호출하고 결과를 반환하지만 cwrap는 C 함수를 래핑하여 호출할 수 있는 JS 함수를 반환한다.
랩핑한 js 파일 webWorker로 실행하기
crwap에 대해서 알아보자
- cwrap를 이용하면 JS 함수처럼 보이지만 내부적으로는 WASM으로 동작하는 함수를 만들 수 있다.
💡 cwrap은 C 함수를 호출하기 위한 JavaScript 함수를 생성하는데 사용된다. 이 함수는 C 함수와 JavaScript 코드 간의 인터페이스 역할을 수행한다.
cwrap의 매개변수는 총 4 가지다. 차례대로
- 호출하려는 C 함수의 이름
- C 함수의 리턴 타입
- C 함수의 매개변수 타입
- 추가 옵션 (this 컨텍스트, 메모리 할당 …)
crwap으로 웹 워커에서 실행할 함수를 만들자
solve.js
- 위의 컴파일 명령어로 만들어낸 js 파일이다.
import Module from "../wasm/sudoku_solve.js";
export async function sudokuSolve(problem: string) {
const instance = await Module();
const sudoku_solve = instance.cwrap("sudoku_solve", "string", ["string"]);
return sudoku_solve(problem);
}웹 워커 스크립트 작성하기
- comlink 라이브러리를 사용했다.
export const wasmWorker = new ComlinkWorker<typeof import("./solve.js")>(
new URL("./solve.js", import.meta.url)
);웹 워커 실행하기
(async function(){
await worker.sudokuSolve(problem);
})()결과
- C 언어로 작성한 코드가 약 4배 정도 빠른 것을 확인할 수 있다.
결론
cpu 집약적인 일이 아니라면, Wasm을 사용하는 것을 지양 해야겠다. 일반적인 형태의 서비스를 제공하는 웹 어플리케이션이라면 웹 워커를 사용하는 것만으로도 UI 스레드의 유휴를 충분히 보장할 수 있다고 생각한다.
Wasm 사용이 꺼려지는 이유는 다음과 같다.
- wasm 포멧으로 컴파일 하는 과정이 어렵고, 지루하다.
- wasm 파일을 가져와서 사용하는 것도 일반적인 형태의 js 함수와 큰 차이가 있다. 함수를 사용하고 싶을 때마다 비동기 작업을 수행해야 한다.
- vite를 사용한다면 아래와 같이 wasm 파일을 사용할 수 있다.
import Module from './excellent.wasm?init';
Module().then((instance)=>{
instance.exports.내함수();
});
// or
(async function(){
const instance = await Module();
const {내함수} = instance;
})()- js로 랩핑된 형태로 컴파일 하는 방법도 있다. 이렇게 랩핑된 js 파일을 이용하면, js 함수처럼 c 모듈을 호출할 수 있다는 장점이 생기지만 wasm이 가진 적은 용량이란 메리트가 없어진다.
import Module from './excellent.js';
(async function createFn(){
const instance = await Module()
const fn = instance.cwrap("add", "num", ["number","number"]);
fn(3,3); // 👈👈👈 6
fn(4,5); // 👈👈👈 9
})()아주 간단한 C 코드를 js로 컴파일 하면 아래와 같이 500줄이 넘는 파일이 생성된다.
🎯 따라서, 정말 필요한 상황이 아니라면 webAssembly를 사용하지 않겠다.
자바스크립트 애호가