24 юли 2011

Game of Life (javascript + html5′s canvas)

Категория: 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 пъти, макар логиката на кода да изглежда по-зле от преди. Не, че преди изглеждаше много красива, но все пак :D

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

Забележка:

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

Тагове: , , ,


23 юли 2011

Прозрение

Категория: 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/

 

 



14 юли 2011

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

Категория: 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 директива, но на практика не стана :D

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

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


Тагове: , ,


13 юни 2011

Mandelbrot + Web Workers

Категория: 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-ите.


Тагове: , , ,


17 май 2011

jslinux

Категория: Dev,WebLucho @ 16:56

How cool is that…

Не съм сигурен как точно работи това, но очевидно javascript енджините вече са ненормално бързи, за да е възможно емиулирането на операционна система в браузър. Ако още не вярвате на очите си, най-добре го разгледайте сами – http://bellard.org/jslinux/

Let the time of browser-based VMs begin!


Тагове: , ,


14 май 2011

Learn to love Javascript

Категория: Dev,WebLucho @ 13:43

Дойде това време от годината, когато човек може да се наслади на изобилие от качествени презентации, благодарение на Google IO. Първото видео, което изгледах беше от Alex Russell, който говори за бъдещия стандарт на Javascript – Harmony. Harmony ще направи опит да очовечи езика, чрез оператори и похвати, които са дефакто-стандарт на повечето функционалните скриптови езици. Все пак не става дума за кардинална промяна, а за „захаросване“ на синтаксиса, така че кодът написан за предни версии на езика да си е напълно валиден.

Както и да е, това не е най-интересното от презентацията. Най-интересното от нея е едно изречение, което характеризира перфектно Javascript и очертава основното различие между този език и останалите скриптови езици:

You don’t create classes that are state with behaivour attached,
you create behaivour that holds the state that it needs.

Enjoy :)


Тагове: ,


11 май 2011

Django за ненормални хора

Категория: Dev,WebLucho @ 23:07

Говорим за Python 2.5+ и Django 1.2+

Какво ще направите ако ви трябва динамично създаден модел?

Първосигналното решение е да създадете класа на модела и под него да добавяте полетата. Това е погрешно поради ред причини, но най-основната е, че базовия клас на моделите (models.Model) се създава посредством метаклас (models.base.ModelBase), който е отговорен за магиите под капака и веднъж щом е създаден класа няма как да добавяте нови атрибути и магиите да сработят с тях.

Второсигналното решение е да създадете наследник на метакласа, който да е отговорен за динамичното създаване на желания модел. Това е доста по-елегантно и в стила на Python, а и ще можете да използвате метакласове най-накрая и да се похвалите на приятелите си :D .


class MetaDynamicData(models.base.ModelBase):

 def __new__(cls, name, bases, attrs):

   newattrs = {'__module__': 'myapp.models'}

   # Да речем, че искате да добавите динамично по един атрибут за всеки месец
   months = [datetime.datetime(2000, x, 1).strftime('%b').lower() for x in range(1, 13)]
   for m in months:
     newattrs[m] = models.IntegerField()

   return super(MetaDynamicData, cls).__new__(cls, name, (models.Model,), newattrs)

class DynamicData(models.Model):
 """
 Dynamic data is cool!
 """
 __metaclass__ = MetaDynamicData

Ако не сте чували за метакласове, най-добре си прочетете документацията, за да разберете какво се случва.

Дотук добре, но какво става ако използвате Sphinx, за да си генерирате автоматично документация за кода?!
Рано или късно ще забележите, че документацията за DynamicData липсва. Липсва, защото Python държи описанието на всеки обект (за по-просто docstring) в магическия атрибут __doc__, а класът DynamicData се генерира динамично от метаклас. За това е нужно да създадем docstring-a в __new__ на метакласа.


class MetaDynamicData(models.base.ModelBase):

 def __new__(cls, name, bases, attrs):

   newattrs = {'__module__': 'myapp.models'}

   newattrs['__doc__'] = "Dynamic data is cool!"

   # Да речем, че искате да добавите динамично по един атрибут за всеки месец
   months = [datetime.datetime(2000, x, 1).strftime('%b').lower() for x in range(1, 13)]
   for m in months:
     newattrs[m] = models.IntegerField()

   return super(MetaDynamicData, cls).__new__(cls, name, (models.Model,), newattrs)

class DynamicData(models.Model):

 __metaclass__ = MetaDynamicData

Сега вече всичко ще е наред и ще може да се похвалите на приятелите си, че знаете какво е __doc__, което ви отрежда място в челната петица на най-образованите Python програмисти и завинаги ви прави по-skilled, от който и да е PHP програмист (самият факт, че пишете на Python стига, май).

За съжаление Джанго не е кръстен на този филм, но пък е горе-долу толкова силен…


Тагове: , ,


Следваща страница »