Jul 24 2011

Game of Life (javascript + html5’s canvas)

Category: Dev,HTML5,WebLucho @ 23:55

Тези дни отново ме загриза съвестта, че не работя по някакъв сайд-проект – мой собствен или open source и за това днес реших да почета и понапиша Game of Life.

Оказа се доста прост алгоритъм с доста интересна история, която и сами може да си прочетете 🙂

Демо може да видите тук: http://dailyffs.com/life/

Сорсът е тук: https://gist.github.com/1102964

Коментарът към сорса от страна на @skanev е тук: https://twitter.com/skanev/status/95213748092026880

Това, което искам да кажа в тази статия е, че колкото и да са бързи съвремените Javascript engine-и и колкото и разни светила и икони на браузър вендорите да се хвалят, че производителността скача многократно от версия до версия, това не значи че не може да забързате всичко още малко много. Цената на “забързването” е “угрозняване” и оптимизиране на кода. В моя конкретен случай – на една функция, която се вика 60000 пъти на преизчисление.

Въпросната фунцкия:


function getLiveNeighbours(id, data) {
  var x = id % canvas.width;
  var y = parseInt(id / canvas.width);

  var cnt = 0;
  for (var i = -1; i < 2; i++) {
    for (var j = -1; j < 2; j++) {
      if ((i != 0 || j != 0) &&
        !(x+i < 0 || x+i >= canvas.width || y+j < 0 || y+j >= canvas.height) &&
        data.data[4*((y+j)*canvas.width+(x+i))] != THE_BLACK) {
        cnt++;
      }
    }
  }
  return cnt;
}

Простата оптимизация на кода включва:

  1. Премахване на извикването на функцията (тялото на функцията се ползва директно) – спестява 60000 извиквания и времето за изпълнение на една итерация пада от 500ms на 270ms
  2. Заменяне на двата вложени цикъла проверяващи за броя на съседни клетки – от 270ms на 150ms
  3. Опростяване на пресмятанията (премахване на умножения) – от 150ms на 60ms
  4. Създаване на локални референции към често използваните данни (вместо постоянни извиквания от типа “obj.data” при изчисленията се създава и използва локална променлива) – от 60ms на 50ms
// (4)
var width = canvas.width*4;
var d = data.data;
var nd = newdata.data;
var cw = canvas.width;
var ch = canvas.height;
var base = 0;

for (var i = 0; i < d.length/4; i++) {
  var x = i % cw;
  var y = parseInt(i / cw);

  var cnt = 0;
  // (1), (2), (3)
  if (x > 0 && d[base-4] != THE_BLACK) cnt++;
  if (x < cw-1 && d[base+4] != THE_BLACK) cnt++;
  if (x > 0 && y > 0 && d[base-4-width] != THE_BLACK) cnt++;
  if (y > 0 && d[base-width] != THE_BLACK) cnt++;
  if (x < cw-1 && y > 0 && d[base+4-width] != THE_BLACK) cnt++;
  if (x > 0 && y < ch-1 && d[base-4+width] != THE_BLACK) cnt++;
  if (y < ch-1 && d[base+width] != THE_BLACK) cnt++;
  if (x < cw-1 && y < ch-1 && d[base+4+width] != THE_BLACK) cnt++;
  ...

В крайна сметка производителността скочи 10 пъти, макар логиката на кода да изглежда по-зле от преди. Не, че преди изглеждаше много красива, но все пак 😀

Разбира се има и още един доста по-умен начин за техническа оптимизация – Web Workers. Те са панацеята на всички проблеми, началото и края, давид и голиат, содом и гомор, ин и ян… за тях може да почетете тази статия – Mandelbrot + Web Workers

Забележка:

  • става дума за проста техническа оптимизация на кода, а не за подобрения на алгоритъма!
  • вероятно оптимизациите в javascript engine-ите не се фокусират върху случаи на извикване на функция 60 хиляди пъти… а би трябвало.

Tags: , , ,


Jul 23 2011

Прозрение

Category: Dev,WebLucho @ 15:17

Преди няколко дни започнах да пиша малко плъгинче (първия ми плъгин акшуъли) за Django, което да филтрира браузъри в зависимост от useragent-а им. Идеята ми беше филтрирането да става в зависимост от версията на браузъра… идея, която работеше преди 5 години. Останах си с тази идея до момента, в който видях няколко useragent-a от мобилни устройства и таблети. Накратко един с един нямат общо, но това което си остава при всички е версията на layout engine-a.

Това е хора. Забравете за IE X или Firefox Y и  т.н., това което ще направи сайта ви да работи на десктоп, телефон и таблет е версията на layout engine-a в комбинация с данните от тези таблички: http://en.wikipedia.org/wiki/Comparison_of_layout_engines_%28Cascading_Style_Sheets%29 и http://caniuse.com/

 

 


Jul 14 2011

Upload на blob като файл чрез AJAX

Category: Dev,WebLucho @ 10:10

Заглавието и на мен не ми говори нищо, за това ще се опитам да обясня с прости думи казуса.

Наскоро забелязах, че при изпращането на голям скрийншот в http://screenshoot.me се случват някакви неприятни неща. По-точно грешка 413 Request entity too large. Оказа се, че хостингът ми не позволява изпращане на POST заявки с параметри по-големи от 1-2мб. За сметка на това пък позволява качване на файлове до 20мб. До тук единственото нещо, което ме притесняваше е дали може да “симулирам” изпращане на файл чрез AJAX. Оказа се че може. FUCK YEAH!

Всъщност може да си префасонирате цялата заявка както ви скимне, което е много готино и същевремено много жалко, защото десетките хиляди фронт-енд дивелъпъри, ползващи jQuery и нямащи понятие от javascript никога няма да узнаят за този факт.

Вероятно бъркам, просто се опитвам да си обясня защо на всяко интервю винаги питат “а ти с jQuery знаеш ли как да работиш” все едно манюъла е 500 страници и ти трябва висше :).

Та реших да разширя леката библиотечка (“парче код” е правилната дума), която ползвам за AJAX обаждания и съответно резултата е тук – https://github.com/lucho870601/ajax-blob-upload

Накратко:

jx.generateBoundary = function(fieldsData) { // Функция, която генерира уникален разделител валиден за всеки фрагмент
  var boundary = parseInt(Math.random()*Math.pow(10, 16)).toString(36) + '' + parseInt(Math.random()*Math.pow(10, 16)).toString(36);
  for (var i = 0; i < fieldsData.length; i++) {
    if (fieldsData[i].indexOf(boundary) > -1) {
      // generate new boundary and check all fields again
      boundary = parseInt(Math.random()*Math.pow(10, 16)).toString(36) + '' + parseInt(Math.random()*Math.pow(10, 16)).toString(36);
      i = 0;
    }
  }
  return boundary;
};

jx.loadFile = function(url, fileData, fileName, callback, opt) {
  var http = this.init(); //The XMLHttpRequest object is recreated at every call - to defeat Cache problem in IE
  if(!http||!url) return;
  var parts = url.split('?');
  var url = parts[0];
  var parameters = parts[1] ? parts[1].split('&') : [];

  var fieldsData = [fileData];
  for (var i = 0; i < parameters.length; i++) {
    fieldsData.push(parameter[i][1]);
  }

  var boundary = this.generateBoundary(fieldsData);
  var body = '';
  for (var i = 0; i < parameters.length; i++) {
    // строим фрагментите за данни
    var p = parameters[i].split('=');
    body += "--" + boundary + "\r\n\
Content-Disposition: form-data; name='"+p[0]+"'\r\n\
\r\n\
"+(p[1] || '')+"\r\n";
  }

  // фрагмента за псевдо-файла
  body += "--" + boundary + "\r\n\
Content-Disposition: form-data; name='" + fileName + "'; filename='" + fileName + "'\r\n\
Content-Type: application/octet-stream\r\n\
\r\n\
"+ fileData + "\r\n\
--" + boundary + "--\r\n";

  http.open("POST", url, true);
  http.setRequestHeader("Content-Type", "multipart/form-data; boundary="+boundary);
  http.setRequestHeader("Content-Length", body.length);
  http.setRequestHeader("Connection", "close");
  ...
  http.send(body);
};

… и получавате данните си като файл накрая.

Кофтито в цялата история е, че не мога да убедя браузъра ми да не слага “charset” и вероятно заради това blob-а пристига в съвсем друг вид. За това пък решението е доста лесно – кодиране на бинарните данни в base64. Неприятно е, че request-а ще набъбне с 1/3 повече и ще трябва да отворите и decode-нете файла сами. На теория декодирането на файла трябва да стане автоматично с Content-Transfer-Encoding директива, но на практика не стана 😀

Удачно е да ползвате този подход не само при гореописания проблем, но и винаги, когато пращате индустриални количества бинарни данни, защото получаването на файл е по-бързо и ангажира по-малко ресурси отколкото получаването на данните като параметър.  Поне така ми се струва 😛

П.П. Преди да имплементирам алтернативното решение се помъчих да увелича лимита на размера на POST заявките с конфигуриране на .htaccess и ini_set на разни магически PHP параметри, но непотръгна.

Tags: , ,


Jul 08 2011

Software Engineering != Software Development

Category: DevLucho @ 17:27

Ще ви го повторя 50 пъти, пък дано отворите wikipedia най-накрая

Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development
Software Engineering != Software Development

Tags: ,


Jun 13 2011

Mandelbrot + Web Workers

Category: Dev,Firefox,HTML5,WebLucho @ 22:28

Обичам фрактална графика и поради липса на по-смислено занимание тези дни, реших да напиша визуализатор за Mandelbrot. Имплементацията ползва готините Web Workers, за да се справи с тоновете сметки и Canvas за да изобрази резултатът на екрана.

48 web worker-a се борят да запълнят 800х600 пиксела пространство и да си призная се справят по-добре от очакваното… е, все още си е бавно, но е 48 пъти по-добре отколкото без възможност за паралелно изпълнение на алгоритъма :D.

Резултатът може да видите тук – http://dailyffs.com/mandelbrot/

А кодът е достъпен тук – https://gist.github.com/1023445

Забележка: работи само с Firefox, защото другите браузъри или нямат web workers или не поддържат предаването на по-сложни обекти от/към worker-ите.

Tags: , , ,


Jun 10 2011

Малко python benchmarking

Category: DevLucho @ 10:45

Наскоро се сблъсках със следния казус:

Как най-ефективно да преобразувам списък от repr на двойки елементи в списък от двойки елементи (т.е. да eval-на всеки string в python-ски tuple). Пример:


["('text1', 'text2')", "('text3', 'text4')", ... "('textn', 'textm')"]

Ето и четирите начина, които тествах:


from time import time
import re

def time_it(n, func, data):
 start = time()
 out = map(func, data)
 print 'time for case %d:' % n, time()-start
 return out

data = map(repr, zip(map(str, range(10**6)), map(str, range(10**6))))
out = []

# 1 - eval на всеки елемент
out.append(time_it(1, eval, data))

# 2 - премахване на ненужните символи
out.append(time_it(2, lambda x: x[2:-2].split('\', \''), data))

# 3 - match-ване на стойностите с регулярен израз за всеки елемент
pattern = re.compile(r'''\('(\w+)', '(\w+)'\)''')
out.append(time_it(3, lambda x: pattern.search(x).group(1, 2), data))

# 4 - match-ване на стойностите с регулярен израз върху всички елементи обединени в един string
pattern = re.compile(r"'(\w+)'")
start = time()
res = pattern.findall(''.join(data))
out.append(zip(res[::2], res[1::2]))
print 'time for case 4:', time()-start

print 'are they all the same?', len(filter(lambda o: o != out[0], map(lambda x: map(tuple, x), out))) == 0

Ето и времената:


time for case 1: 15.3229999542
time for case 2: 2.14499998093
time for case 3: 1.76999998093
time for case 4: 1.20600008965
are they all the same? True

Познах им класацията по бързодействие още преди да ги напиша :).

Естествено, най-правилният начин е този, който първи идва в главата на човек – eval. За съжаление обаче, ще трябва доста да почакате! Дори и да се направите на хитри и да пробвате със следния код (който е още по-грозен от вариант номер 4)


eval(repr(data).replace('"', ''))

пак времето нужно за изпълнение е около 10 пъти повече от вариант номер 4.

Макар че четвъртият пример е най-ефективен, не го препоръчвам поради ред причини, но най-вече защото кодът не се ръководи по форматa на данните, а просто агрегира всичко, което е между кавички. За това пък третият вариант е доста близък по време до четвъртия и за разлика от него се ръководи по структурата на данните, не прави един огромен текстов низ и е доста по-кратък и разбираем. Вариант номер 2 го забравете, че съществува 😉

Та, в заключение – гледайте да използвате по-рядко eval и да балансирате добре между разбираемост и бързодействие.

P.S. Eval is Evil by default… so never use it for evaluating external code or else your program will execute someone else’s code 🙂

Tags: , ,


Jun 05 2011

Как работи един голям не-ентърпрайз софтуерен проект

Category: DevLucho @ 16:31

Преди 2 седмици попаднах на това видео от PyCon 2011, в което създателите на едно от най-големите Django приложения – Disqus, разказват как работи то. Disqus е embeddable платформа за коментиране, която има над 500 милиона уникални посетители месечно. Само поради този факт си струва да изгледате видеото… освен това ползват и разработват доста хитри туулове, с които е добре да се запознае човек.

Другото интересно нещо, което намерих е fork на haystack със spatial support – https://github.com/dannercustommade/django-haystack

Точно си мислих да започна да пиша разширение за haystack, което да поддържа новите spatial функции в solr и се оказа, че съм закъснял с 2 месеца. Карай.

Оказа се, че плъгинът не е напълно завършен и spatial функциите не работят с последната версия на solr, така че ще го форкна и ще пробвам да го пооправя.

п.п. haystack е django плъгин за работа със solr и други full-text search engines.


Tags: , ,


« Previous PageNext Page »