Разгоняем JavaScript вместе (Внимание, конкурс!)

[belator]

Вы сначала опубликуйте решение прошлой задачи thecodeil.com/
Оно уже у вас висит 3 года, а решение вы вывесить не удосуживаетесь.

[printf]

А она остается в силе. Это бесконечная вялотекущая задача, нам еще присылают решения, и специально обученная девочка их проверяет (очень медленно).

Именно поэтому теперь у конкурса есть срок окончания.

[shodan]

А у нее решения, формально говоря, нету.

Потому что твое видение «as good as you would expect a good libc to implement such functions» не совпадает с видением организаторов.

Хуже, я подозреваю, если аккуратно обернуть стандартные strcpy/strcat, решение не проканает.

И пробовать играть в эту телепатию неинтересно совсем, тк. итерация длится 2 месяца (?!!!) и в ответ приходит стандартная отписка.

[mwizard]

На вот это решение спустя два месяца был получен ответ «Очень слабое решение, посмотрите на типичный список ошибок» — и ссылка на вот это!

Решение — libstr.c

#include "libstr.h"

#include <stdlib.h> /* size_t, realloc() */
#include <string.h> /* memmove(), strlen() */

BOOL str_cpy(char (*(*const result)), char const (*const value)) {
    char *buffer;
    size_t length;
    
    if (result && value) {
        length = strlen(value) + 1;
        
        if ((buffer = realloc(*result, length))) {
            memmove((void*) buffer, (const void*) value, length);
            *result = buffer;
            
            return YES;
        }
    }
    
    return NO;
}

BOOL str_cat(char (*(*const result)), char const (*const value)) {
    char *buffer;
    size_t result_offset;
    size_t value_length;
    
    if (result && value) {
        result_offset = strlen(*result);
        value_length = strlen(value) + 1;
        
        if ((buffer = realloc(*result, result_offset + value_length))) {
            memmove((void*) (buffer + result_offset), (const void*) value, value_length);
            *result = buffer;
            
            return YES;
        }
    }
    
    return NO;
}

Решение — libstr.h

#ifndef __LIBSTR_H__
#define __LIBSTR_H__

#ifndef __BOOL_DEFINED 
#define __BOOL_DEFINED

#define BOOL  signed char
#define NO    ((BOOL) 0)
#define YES   (!NO)
#endif // !defined(__BOOL_DEFINED)

BOOL str_cpy(char **const result, char const *const value);
BOOL str_cat(char **const result, char const *const value);

#endif // !defined(__LIBSTR_H__)

Решение — hola.c

/* Copyright (C) Hola 2012, 2013
 *
 * Welcome to TheCodeIL.com Challenge!
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

#include "libstr.h"

int str_printf(char **const result, const char *const format, ...);
int str_free(char **const dst);

int str_printf(char **const result, const char *const format, ...) {
    char *buffer;
    int length;
    va_list vargs;
    
    if (!result) return -1;
    if (!format) return -1;
    
    va_start(vargs, format);
    length = vsnprintf(NULL, 0, format, vargs);
    va_end(vargs);
    
    if (!(buffer = realloc(*result, length + 1))) return -1;
    
    va_start(vargs, format);
    vsprintf(buffer, format, vargs);
    va_end(vargs);
    
    *result = buffer;
    
    return 0;
}

int str_free(char **const result) {
    if (!result) return -1;

    free(*result);
    
    return 0;
}

int main(int argc, char *argv[])
{
    char *s = NULL;
    str_cpy(&s, "Hola Hola");
    str_cpy(&s, s+5);
    str_cat(&s, " World");
    str_printf(&s, "%s!", s);
    puts(s); /* result: "Hola World!" */
    str_free(&s);
    return 0;
}

[staker]

(Я не работаю в Hola)
У вашего решения есть несколько проблем:

При запуске «str_cpy(&s, s+5);» ваш memmove читает из памяти которая вам уже не принадлежит.

Аналогично при запуске str_cat(&s, s+5);

[mwizard]

ладно, окей, вы правы :C

[printf]

Да, прошлая задача реально неудачная. Я сам на эту тему столько копий сломал.

Но так уж исторически сложилось.

В этот раз всё лучше: есть и способ валидации, и сроки окончания.

[shodan]

Задача приемлемая, можно и с этим жить. На то ведь оно и заманушный конкурс, а не Идеальное ТЗ.

Но вот организация конкурса, скорость и качество фидбэка просто чудовищные.

[printf]

Да. Там вообще была гуманитарная катастрофа, никто не ожидал такого потока писем, думали – ну откликнется человек сто. Ошиблись очень сильно.

[forgotten]

Без кейсов тестирования — это совершенно бессмысленное соревнование.

[printf]

Тесты в репозитории же.

[forgotten]

Это юнит-тесты. А я про те тесты, которыми будет измеряться скорость.
Очевидно, что под разные кейсы использования можно оптимизировать код по-разному, т.е. оптимизировать одни операции в ущерб другим.

[printf]

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

Если их раскрыть, то появится возможность написать код, который очень быстро и хорошо проходит все тесты – и только их, т.е. ни в каком другом случае не работает. Формально это является решением.

На олимпиадах по программированию тоже никогда не открывают приемочные тесты, т.к. теряется всякий смысл.

[forgotten]

На олимпиадах по программированию правильность измеряют, а не скорость.
Затачивать код под неизвестный кейс — бессмысленная затея.

[printf]

Именно. Поэтому не надо затачивать, надо переделывать код, чтобы он в принципе работал быстрее. Как в настоящем проекте. В продакшене никаких тестов нет, там юзеры.

Вырожденных дурацких случаев вида "%d%d%d 250 тысяч раз" в финальном тесте не будет.

На олимпиадах по программированию правильность измеряют, а не скорость.

На олимпиадах органичивают снизу скорость, измеряют корректность.
Мы ограничиваем снизу корректность, измеряем скорость.
Такая вот анти-олимпиада.

[Zibx]

Основной вопрос — другой. Нужно знать какой вариант будет тестироваться:
а) "%d %m %h"( date ) * вызов этого 1000 раз
б) вызов 1000 раз "%d %m %h"( date ) с полным перезапуском
в) вызов 10 раз любого из этих кейсов.

Для всех этих трёх случаев принцип оптимизации разный.
Ещё там есть такой забавный параметр, как locale, который можно указывать для каждого случая.
Если эта функция будет действительно использоваться на продакшене, то было бы намного оптимальнее сразу поменять синтаксис и сделать

var format1 = dateFormatter(template, locale,options);
format1(date)//*1000 вызовов

Все остальные варианты являются заранее не оптимальными бай дезайн.

[printf]

Да запросто, можно поменять. Хотя по большому счету разницы нет, оно может внутри оригинального вызова то же самое ведь делать.

Направление верное.

[Zibx]

Оно может кэшировать от template. Это потеря ln(O) на каждом вызове, но это мелочь. А вот когда приходит locale — всё меняется. Тут при кешировании сложность O, либо оно на самом деле использует этот переданный locale и опять же ln(O), потому я и пишу что генератор функции является оптимальным, а остальное порождает некоторый оверхэд.

[Jabher]

del

[turbo_exe]

ребят, как человек только поверхностно знакомый с Node.js, хотел бы спросить: а какие такие приемущества он предоставляет, что вы тритите своё время на оптимизацию его функций вместо того, чтобы писать на любом другом интерпретируемом языке (php, python, ruby)? многие из них транслируются в байт-код и имеют нечто наподобие JIT, что позволяет забыть об оптимизации работающего не кривого кода.

[forgotten]

Во-первых, нод весьма низкоуровневый, в отличие от.
Во-вторых, нод принципиально заточен под клиент-сервер схему, а не «выполнить скрипт и умереть».
В-третьих, нод — событийно-ориентированный и неблокирующий, т.е. заставляет писать в асинхронных парадигмах, а это, как показывает практика, парадигма, в которой достигается максимальная производительноть (проблема 10К соединений).
В-четвёртых, нод/JS и так производительней абсолютного большинства скриптовых языков — сейчас идут напряженные баталии о том, можно ли от него добиться производительности статически типизированных компилируемых языков.
В-пятых, количество кода на NodeJS растёт просто экспоненциальными темпами, JS давно уже самый популярный язык на гитхабе.

Поэтому ваш вопрос нужно ставить иначе: а какие преимущества дают php/python/ruby, чтобы писать на них?

[bolk]

Про низкоуровневость расскажите поподробнее, очень любопытно послушать.

[printf]

А чего рассказывать, стандартная библиотека Node.js практически как в Си.

Высокоуровневые примитивы появляются в библиотеках (например, connect).

[bolk]

Ну так какие отличия-то от Пайтона, ПХП, Руби?

[printf]

Вы даже не представляете себе стандартную библиотеку Питона, правда?

В стандартной поставке Питона – целая куча структур данных, алгоритмов, поддержка сетевых протоколов, форматов файлов, разнообразного кодирования, в т.ч. поддержка записи аудиофайлов (!), UI тулкит (!), встроенная СУБД.

А в ноде – чтение-запись файлов (== потоков байт), простенький веб-сервер и биндинги к openssl.

[bolk]

Неправда, я на нём пять лет пишу. Наличие высокоуровневых вещей никак не противоречит наличию низкоуровневых. А нода просто не обросла нормальными библиотеками, очевидно, и только.

[printf]

Да-да, и Си тоже вот как-то «не оброс».

[bolk]

Смеётесь что ли? Поищите к нему библиотеки, всё есть.

[forgotten]

«Уровень» языка прежде всего определяется уровнем абстракции, которым приходится оперировать.
Ваш коммент заминусован потому, что, по вашей логике, Си — высокоуровневый язык, а это не так, несмотря на количество имеющихся библиотек.

Нод заставляет писать на максимально близком «к железу» уровне, насколько это вообще возможно без потери кроссплатформенности. Практически всё написано через бинарные буферы; модуль http заставляет работать со всеми кишками http, даже POST-данные нужно через Stream грузить; и тому подобное. Это не вопрос наличия библиотек — это вопрос того, какими структурами данных и операциями вам нужно манипулировать в «голом» языке.

[bolk]

Нет, я не считаю Си высокоуровневым. Но я не считаю Джаваскрипт низкоуровневым и именно к этой мысли и я пытался подвести собеседника. На «голом» Пайтоне операции примерно те же, есть язык, а есть набор модулей к нему — это разные вещи, даже если распространяются вместе.

[forgotten]

А мы не про джаваскрипт, а про нод.

[bolk]

Тогда давайте вернёмся к началу. Диалог такой получается:

— Как человек только поверхностно знакомый с Node.js, хотел бы спросить: а какие такие приемущества он предоставляет?
— Нод весьма низкоуровневый, в отличие от.

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

[Zibx]

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

[bolk]

Безусловно, ровно как в PHP, Python, Ruby. И любых фреймворках на них.

[forgotten]

Преимущество в том, что **заставляет** писать код, заточенный под максимально эффективное взаимодействие с системой. В чём преимущество в контроле за памятью в C?

Конечно, не для всех это преимущество.

[bolk]

Каким это таким магическим образом заставляет? Низкоуровневостью? Обычный программист скопипастит библиотеку из сети, не задумываясь, да ещё и плеваться будет.

Кстати, «С» — это предлог, а язык — «Си».

[turbo_exe]

нет аргументов? дое*ись к грамматике!

[bolk]

Аргументы были первым абзацем.

[printf]

Нода на многих задачах изначально быстрее, чем php, python и (особенно) ruby.

Забыть про оптимизацию не позволяют масштабы проекта, увы.

[haskel]

Чтобы не быть голословным, киньте пруф сравнения с php 5.4.

[haskel]

Я действительно не понимаю в каком месте node уделывает php в производительности, киньте, плз, ссылку. Я не фанат php, я люблю scala. Мне просто интересны реальные тесты производительности, а гугл таких тестов не дает.

[printf]

Можно потестировать самому. Можно погуглить.

Первый результат в гугле. По ссылке V8 уделывает по скорости пхп непонятно какой версии в среднем в 9 раз.

[haskel]

Самое интересное в этом бенчмарке, что в нем не показано, какой код против какого тестируют. То есть получаем 9 попугаев в вакуме. Что-то здесь не так.

[printf]

Ну приехали, там же прямо на этой странице ссылки на все исходники.

(Ссылки это синие такие буковки, в них мышкой кликают.)

[haskel]

Спасибо, сразу не приметил.
Тем не менее цитата с первой страницы теста: «Measurement is highly specific». И дальше разъяснение, что тест не учитывает вообще никакой специфики языка и меряет лишь производительность игрушечной программы. Это также легко понять если посмотреть в исходники.

Теперь понятно, почему в условиях конкурса "«Эталонный» бенчмарк является восхитительной тайной."

[printercu]

benchmarksgame.alioth.debian.org/u32/benchmark.php?test=all&lang=v8&lang2=php&data=u32 можно поиграться.

[intet]

И вообще почему все так стремятся уйти со статистически типизированных языков к динамически-типизированным?
Не спорю, на маленьких проектах динамическая типизация выглядит привлекательно. Но когда проект вырастает, и количество постоянно работающих над ним программистов становиться больше одного, то постоянно возникают проблемы — 'а что возвращает код написанный другим программистом?'.
Приходиться либо отвлекать соседа и спрашивать, либо самому тратить время и разбираться. А уж рефракторинг и изменение возвращаемых значений и вовсе превращается в головную боль.

[Zibx]

Для решения этой проблемы существуют IDE и соглашение вести документацию.

[Maccimo]

Да как-то не особо с этим в IDE.
Вот в этом примере список доступных полей однозначен, однако же PhpStorm в code completion покажет список всех полей всех классов. Нерелевантный bar — в том числе.

Скрытый текст

function f() {
    return {
        foo: "Lorem ipsum"
    }
}

function g() {
    return {
        bar: 42
    }
}

var
   x = f();

x.| // ⇐ cursor here

[asavin]

jsdoc улучшает работу PhpStorm, попробуйте.

[tenshi]

jsdoc — это прикрученная сбоку кривая статическая типизация. Лучше уж typescript.

[forgotten]

Неправда. Вот такой, вполне себе «прямой» jsdoc-коммент

var MyClass = function () {}
extend(MyClass.prototype, /** @lends MyClass.prototype */ {
 // methods
});

прям драматически повышает навыки ВебШторма

[intet]

Но ведь необходимость в комментировании — это признак плохого кода. Код должен быть читаем без всяких посторонних (часто неактуальных) комментариев.

[Zibx]

Сразу как код начнёт легко читаться роботами — он станет ими же и писаться.

[freeart]

Как большой поклонник js я был бы рад даже слабой типизации. Приятно было бы написать (count int, data obj) и даже не думать о проверках.

[printf]

Можно TypeScript для этого прикрутить. Он медленный, правда, когда много кода.

[mwizard]

Ребята, ваш прошлый конкурс — бессовестнейшее разводилово. Чем отличается этот?

[printf]

Вот список ребят, которые получили призы. Несколько человек остались у нас работать, могу познакомить.

А на обиженных традиционно воду возят.

[mwizard]

Нет, вопрос не по списку ребят, которые «получили призы». Вопрос в том, чем тот конкурс отличается от этого?

Я был бы крайне признателен, если бы вы, или Рути, указали слабые стороны в решении, которое отправлено выше. В решении, которое настолько слабое, по словам Рути, что даже не нужно уточнять, в чем именно оно слабое — ведь это и так очевидно. Просто найдите хоть что-то, к чему можно прицепиться, что нарушало бы правила вашего же конкурса, для того, чтобы подтвердить свою позицию.

[printf]

Можно написать Рути и спросить. Адрес же есть.

Сделаем проще: я завтра спрошу у техдира и опубликую его ответ. Годится?

Отличается значительно: язык другой, задание другое, приемочные критерии объективные.

Есть также сходство: никто не заставляет в этом участвовать. Даже вас. Особенно вас. Мы вообще против насилия и за личностные свободы, что бы этот набор слов ни значил.

[cL1Nk3r]

Задача: разогнать оригинальную функцию strftime в 50 раз

Интересно, данный код вообще возможно ускорить в 50 раз? У вас уже есть пример того, как это сделать?

[printf]

Да. Выложу, когда все закончится.

Есть еще какие-то наброски с нативным кодом (модуль Node на C++), но пока JS уделывает этот гибридный вариант.

[mwizard]

Почему не публикуете свою вторую задачу — сделать cujojs/when, самую быструю библиотеку Promise/A+, быстрее хотя бы в 5 раз?

[printf]

Всему свое время.

[zalatov_a]

Может немного не в тему, но тоже про оптимизацию скорости работы с датами.
Как-то вспомнилось…

Необходимо было сгенерировать карту сайта с количеством элементов около 500 000.
Генерация выполнялась очень медленно — порядка 30-40 секунд.
Путём анализа был выявлен участок, замедляющий код.
Это была функция date('c') — вывод даты в формате стандарта ISO 8601, напр. 2004-02-12T15:19:21+00:00.

Так как в базе хранился timestamp изменения записи, то нашлось очень лаконичное решение:

$date{10} = 'T';// Заменяем пробел между датой и временем на букву T
$date .= '+00:00';// Добавляем в конец для совместимости с форматом

Таким образом удалось сократить время ~15 раз – до 2-3 секунд.

[KlonD90]

Победит тот кто напишет на c модуль для javascript?

[azproduction]

И скомпилит emscripten в asm.js

[printf]

Необязательно. Простой вызов из libc чуть быстрее, конечно, но не настолько.

Вообще мне самому интересно.

[olegdunkan]

Стратегически, мне видится следующая оптимизация функции strftime, для некого входного сочетания форматеров (%x1, %x2 и т. д.) генерируется функция, которая потом вызывается каждый раз когда встретится такое же сочетание форматеров. Эта функция будет возвращать результат выражения, состоящего максимум из операций конкатенации и обращений к объекту локализационных параметров, плюс вычисления связанные с смещением зоны. Оверхед только при первом вызове strftime для нового сочетания, на генерацию такой функции, зато потом вызывается единственная функция. Мы сразу уходим от регулярного выражения, функции replace и последующих вызовов функций для каждого форматера

[Zibx]

Собственно возникает вопрос тестирования скорости, может каждый раз будет исполняться холодный старт и компиляция функции под конкретный кейс даст только оверхэд.

[olegdunkan]

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

[godlin]

Вот, например, отказ от проверки всех RequiredDateMethods у данного объекта в методе quacksLikeDate (с учетом того, что данный метод внутри модуля используется только для различения даты и локали), ускоряет strftime примерно раза в два.
Таким образом, встает вопрос:
а действительно ли надо делать такую проверку или достаточно просто проверить, локаль это или не локаль?

[RubaXa]

Тесты же есть.

[monolithed]

Мне одному кажется, что 500$ за решение этой задачи маловато?

[Ilusha]

Не одному)

[Zibx]

Цена написания одной функции нормальная, но тем кто может её ускорить в 50 раз — лень заниматься этим за $500.

[Ilusha]

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

[RubaXa]

printf, я может что-то не понял, но в 50 раз, это точно не ошибка?
Или может мы как-то по другому «разы» меряем?

Вот простой бенчмарк для strftime('%A');:

Код теста

var strftime = require('./strftime').strftime;
var Benchmark = require('./benchmark');
var days = 'Sunday Monday Tuesday Wednesday Thursday Friday Saturday'.split(' ');
var noop = function () { };

(new Benchmark.Suite)
	.add('noop', function () {
		noop();
	})
	.add('new Date', function () {
		new Date;
	})
	.add('new Date.getDay', function () {
		days[(new Date).getDay()];
	})
	.add('strftime', function () {
		strftime('%A');
	})
	.on('cycle', function (evt) {
		console.log(evt.target + '');
	})
	.run()
;

Результат

noop x 77,132,969 ops/sec ±3.00% (91 runs sampled)
new Date x 8,094,124 ops/sec ±2.08% (94 runs sampled)
new Date.getDay x 5,264,363 ops/sec ±3.44% (89 runs sampled)
strftime x 618,999 ops/sec ±2.81% (92 runs sampled)

«Разогнать в 50 раз» — это значит получить ~30,000,000 ops/sec ?!
Можете написать, каким образом устроен ваш бенчамарк и что такое 50 раз?

[printf]

Ну да.

Бенчмарк устроен примерно так же, а 50 раз это ориентировочная цифра. Она, конечно, зависит от машины, на которой это все выполняется, и от других вещей.

[godlin]

Ну, вот, под ГуглоХромом я вчерась разогнал где-то раз в 7…

[RubaXa]

От машины будет зависеть только максимальное ops/sec, а вот разница между new Date и strftime будет примерно такая же, так что даже в теории вашу функцию нельзя убыстрить больше чем в 10 раз, хотя и эта цифра утопия. Либо нужно приложить к условиям, как именно будут выводится эти «50 раз», ну и массив входных данных.

[godlin]

Я полагаю, такая цифра возможна, если мы оперируем большим количеством данных в одной сессии, т.е. мы можем кэшировать результаты каких-то функций и таким образом значительно ускорить их выполнение по сравнению с оригинальной функцией. При этом на маленьких выборках фукция с кэшированием может работать хуже.

[RubaXa]

Это я всё понимаю, просто условия мутные…

[printf]

Если в теории что-то нельзя сделать, а на практике можно, значит, теория неверна.

[RubaXa]

Я очень надеюсь, что в конце конкруса вы покажите победителя, у которого функция strftime('%A') будет быстрей в «50 раз».

[eme]

Да и сделайте адекватную приемку результатов. Чтобы все могли видеть, кто, что и в каком виде выполнил\отправил.
С удовольствием бы потратил время, но отталкивают некоторые вещи:

1. Если никто так и не достигнет желаемого результата, что тогда?
2. Если будут решения с одинаковой производительностью(увеличенной >50 раз), что тогда?
3. Если будет код которые замедляет всё остальное приложение, что тогда?

[printf]

1. Мы просто отсортируем все присланные решения по скорости.
2. Не знаю, разберемся по мере возникновения проблемы.
3. Какое остальное приложение?

[eme]

Ну вы же скрипт не в консоли используете.
Я вот возьму и у Object расширю прототип, да побольше. Захламлю глобальный скоуп.
Так что по итогу функция работать быдет быстрее, а например если это вэб сервер, то ответы отдавать станет в 5 раз дольше.

[printf]

Мне было бы интересно на это посмотреть.

[eme]

Вы же не конкурс плохих решений устраиваете.

[Zibx]

А это хитрый план — замедлить нативную функцию в 50 раз ^_^.

[azproduction]

Максимум выжал 21х без кэша — 3.3kk op/sec для %Y-%m-%dT%H:%M:%S%z. С FIFO кэшом x200 — 33kk op/sec. При 100% промахе кэша производительность деградирует до 18х.

Буст в 50 раз даже ручным кодом не удалось получить для паттерна выше. Для получения 50x без кэша/тредов точно не обойтись.

Заводилось в 1 ядро: Node v0.10.28 @ V8 3.14.5.9.

[bakhirev]

Что такое FIFO кэш и как его использовать?

noop x 86,135,301 ops/sec +1.41% (93 runs sampled)
new Date x 8,144,440 ops/sec +0.39% (97 runs sampled)
new Date.getDay x 5,672,311 ops/sec +0.27% (98 runs sampled)
strftime x 20,762,146 ops/sec +0.21% (100 runs sampled)

[azproduction]

Короткий кэш из 5 итемов, к примеру, по ключу {format, timestamp[, locale]}. Lookup итема происходит без «Хэш-индекса» ака var index = {}; те просто for-ом по массиву, иначе будут тормоза с удалением добавлением итема в «индекс». Потом есть pointer который указывает в какую ячейку кэша нужно положит будущий результат. Всей этой структурой мы добиваемся того, чтобы не было GC на объектах кэша и не тратим время на конструирование составного ключа.

Большие кэши не нужны тк эта функция зависит от времени и каждый раз на вход могут подаваться разные знаения -> много промахов+тормоза.

var cache = [{
    value: null,
    format: null,
    ts: null
}, ...];
var pointer = 0;

var ts = date.getTime();

// lookup
for (var i = 0; i < cache.length; t++) {
    if (cache[i].format === format && cache[i].ts === ts) return cache[i].value;
}

// put
var value = strftime(format, date);
if (pointer > cache.length) pointer = 0;

cache[pointer].format = format;
cache[pointer].value = value;
cache[pointer].ts = ts;

pointer++;
return value;

[eme]

Дело явно не в оптимизации кода, у меня например пустой модуль возвращающий строку, отличается от noop на треть.

noop x 100,616,486 ops/sec ±1.50% (90 runs sampled)
new Date x 9,493,274 ops/sec ±0.34% (98 runs sampled)
new Date.getDay x 6,632,312 ops/sec ±0.17% (101 runs sampled)
strftime x 194,136 ops/sec ±0.31% (98 runs sampled)
strftime empty module x 70,104,615 ops/sec ±1.83% (91 runs sampled)

[w0den]

printf,
Скажите пожалуйста, если не секрет, многие ли решили задачу?

[printf]

До этого задание в таком же точно виде использовалось для приема на работу, несколько человек решили.

За первый день после этого поста мы еще пару решений получили по почте, уже в рамках конкурса. Одно очень классное вроде.

В общей сложности пока человек 5-6 справились на «отлично».

[w0den]

Спасибо за ответ. Сейчас попробую решить задачку — может получится что-то полезное.

[RubaXa]

Я конечно не настоящий сварщик, но увеличить скорость более чем в 8 раз мне так и не удалось:
gist.github.com/RubaXa/4271cac9c0d39fc892c8

P.S. Наверно тут нужно использовать какую-то черную магию, которая позволила бы увеличить скорость самого js:

native vs. strftime

var strftime = require('./strftime').strftime;
var Benchmark = require('./benchmark');

(new Benchmark.Suite)
	.add('native', function () {
		var date = new Date(Math.random() * 1e10);
		var hours = date.getHours();
		var mins = date.getMinutes();
		(hours > 9 ? hours : '0' + hours) + ':' + (mins > 9 ? mins : '0' + mins);
	})
	.add('strftime', function () {
		strftime(format, new Date(Math.random() * 1e10));
	})
	.on('cycle', function (evt) { console.log(evt.target + ''); })
	.on('complete', function () {
		var fastest = this.filter('fastest')[0];
		var slowest = this.filter('slowest')[0];
		console.log(fastest.name + ' is fastest (' + (fastest.hz/slowest.hz) + ')');
	})
	.run({ async: true })
;

native x 4,352,575 ops/sec ±2.01% (89 runs sampled)
strftime x 263,963 ops/sec ±1.79% (93 runs sampled)
native is fastest (16.489356157880962)

[w0den]

Ну, особая магия тут не нужна — хватит и обычной :)

Вот что мне удалось (не обращаете внимание на количество операций в секунду, ибо ноут не сильно шустрый):

>> original x 80,919 ops/sec ±2.06% (95 runs sampled)
>> my_ver_2 x 4,306,567 ops/sec ±0.56% (92 runs sampled)
The "my_ver_2" is 53x faster than "original"

Это результат теста для:

bench.add('strftime', function () {
    return strftime('%Y-%-m-%0dT%H:%_M:%S%z');
});

bench.add('my_ver_2', function () {
    return my_ver_2('%Y-%-m-%0dT%H:%_M:%S%z');
});

Единственная проблема, что только для строки %H:%M:%S скорость не достаточно высока:

>> original x 185,497 ops/sec ±1.88% (89 runs sampled)
>> my_ver_2 x 4,177,974 ops/sec ±0.59% (96 runs sampled)
The "my_ver_2" is 23x faster than "original"

Надеюсь, до завершения конкурса я найду время чтобы заниматься этим, так как задача действительно интересная. А насчёт конкурса, чего бы не говорили другие — кажется с ним всё в порядке.

[RubaXa]

Я вижу, что у вас не передается вторым параметром время, а значит вы берете его просто как new Date, так что рискну предположить, у вас там кеширование. Ибо как видно из кода под спойлером, Native код не сильно то и быстр, каждый дополнительный вывозов Date-метода резко понижает производительность.

[w0den]

То есть, Вы хотели сказать что my_ver_2() не генерирует новую дату? Если это так, вот такой тест:

setInterval(function() {
    console.log('strftime >> ' + strftime('%Y-%-m-%0dT%H:%_M:%S%z.%L'));
    console.log('my_ver_2 >> ' + my_ver_2('%Y-%-m-%0dT%H:%_M:%S%z.%L'));
}, 0);

Возвращает такой результат:

strftime >> 2014-5-21T22:10:33+0300.635
my_ver_2 >> 2014-5-21T22:10:33+0300.635
strftime >> 2014-5-21T22:10:33+0300.651
my_ver_2 >> 2014-5-21T22:10:33+0300.651
strftime >> 2014-5-21T22:10:33+0300.667
my_ver_2 >> 2014-5-21T22:10:33+0300.667
strftime >> 2014-5-21T22:10:33+0300.682
my_ver_2 >> 2014-5-21T22:10:33+0300.682
strftime >> 2014-5-21T22:10:33+0300.698
my_ver_2 >> 2014-5-21T22:10:33+0300.698
strftime >> 2014-5-21T22:10:33+0300.713
my_ver_2 >> 2014-5-21T22:10:33+0300.713
strftime >> 2014-5-21T22:10:33+0300.729
my_ver_2 >> 2014-5-21T22:10:33+0300.729
strftime >> 2014-5-21T22:10:33+0300.745
my_ver_2 >> 2014-5-21T22:10:33+0300.745
strftime >> 2014-5-21T22:10:33+0300.760
my_ver_2 >> 2014-5-21T22:10:33+0300.760
strftime >> 2014-5-21T22:10:33+0300.777
my_ver_2 >> 2014-5-21T22:10:33+0300.779
strftime >> 2014-5-21T22:10:33+0300.791
my_ver_2 >> 2014-5-21T22:10:33+0300.791
strftime >> 2014-5-21T22:10:33+0300.807
my_ver_2 >> 2014-5-21T22:10:33+0300.807

Или я неправильно Вас понял?

[RubaXa]

Написал в личку, чтоб тут не мусорить.

[w0den]

Чтобы всё было справедливо и понятно — printf, скажите пожалуйста, для следующего теста, новая функция всегда должна работать в 50 раз быстрее?

Benchmark

function runBenchmark(str, date) {
    (new Benchmark.Suite)
        .add('strftime', function() {
            var dt = date ? (new Date(Math.random() * 1e13)) : null;
            return strftime(str, dt);
        })
        .add('new_strftime', function() {
            var dt = date ? (new Date(Math.random() * 1e13)) : null;
            return new_strftime(str, dt);
        })
        .on('cycle', function(evt) {
            console.log('>> ' + evt.target);
        })
        .on('complete', function() {
            var fastest = this.filter('fastest'),
                slowest = this.filter('slowest'),
                times = parseInt(fastest.pluck('hz') / slowest.pluck('hz')),
                args = str + (date ? ', date' : '');

            console.log(fastest.pluck('name') + '(' + args + ') runs ' + times + 'x faster\n\n');
        })
        .run();
}

var strings = ['%Y-%-m-%0dT%H:%_M:%S.%L%z', '%H:%M:%S', '%A'];
for (var i = 0; i < strings.length; i++) {
    runBenchmark(strings[i], true);
    runBenchmark(strings[i], false);
}

ps. Было бы замечательно, если бы Вы показали результаты этого бенчмарка для Вашей функции.

[printf]

Ох, а можно то же самое продублировать на английском в почту конкурса? Я в ближайшие три-четыре дня оффлайн. Спасибо.

[KlonD90]

Вопрос интересует и меня: не могли бы результаты тут опубликовать?

[tenshi]

Вы это, напишите, что всё надо писать на английском, ибо проверять это будет не русскоговорящий человек.
Не понятно требование реализовать в точности такой же интерфейс. Все эти однобуквенные сокращения просто невозможно запомнить — приходится безконца лазить в шпоргалки. Кроме того, передавать паттерн при каждом вызове — не удобно и несколько медленнее.
Такое апи было бы куда предпочтительнее:

var formatTime = $jin.date.formatter( 'Weekday, YYYY-MM-DD hh:mm' )
formatTime( new Date ) // Thursday, 2014-05-23 11:45

[printf]

API: было выше.

Английский: верное замечание, как-то не пришло в голову указать язык – страница же вся на нем. Это не критично, надо будет – переведем.

[RubaXa]

И так, наконец-то объявлены результаты конкурса и победителем стал… сам бенчмарк :]

Получилось это следующим образом, в начале теста наполняется массив из 1000 уникальный дат, а дальше от теста к тесту бегают по нему, а это значит, что простым присваиванием результата форматирования в объект даты, позволит выиграть этот конкурс. И даже больше, если бы вы просто вначале оригинальной функции strftime написали:

то получили бы ускорение примерно в 150 раза, это почти в два раза быстрей «победителя».

Самое интересное, такого не ожидал никто (судя по коду), чего угодно, но не такого :] По этому я не поленился и сделал честный бенчмарк, чтобы выявить настоящего победителя. Честный тест состоит из суммы разгона функции на полностью уникальных данных и на 1000 timestamp.

В итоге шестерка победителей выглядит следующим образом:

  #1. siranthony        (7.451 + 12.018)/2 = 9.735
  #2. newbiecraft       (10.010 + 8.633)/2 = 9.322
  #3. mapostol          (10.005 + 8.256)/2 = 9.131
  #4. lexich121         (11.864 + 3.225)/2 = 7.545
  #5. nikitin.alexandr  (10.173 + 4.295)/2 = 7.234
  #6. dm.ashurov        (10.257 + 4.020)/2 = 7.139

Это те юзернеймы, которые занимались именно оптимизацией функции strftime. Из результатов легко заметить, что ни о каких 50 раз речи не идет, но это все равно крутейший результат, с чем я и поздравляю ребят.

github.com/RubaXa/challenge_strftime — тут можно посмотреть каждый тест по отдельности и результаты других участников.

В конце хотелось бы узнать мнение организаторов конкурса (printf) по этому поводу и почему выбран именно такой «тест»?

[printf]

Мнение очень простое — можно сделать целый ворох бенчмарков, запустить их на куче различных конфигураций и получить очень разнообразные результаты.

Прямо сейчас, во время написания этого сообщения, я запустил предлагаемый «честный бенчмарк» — и получил совсем-совсем другую шестерку победителей: у меня вариант kuchumovn в random-тесте победил siranthony, например.

Наш тест вовсе не идеальный, никто и не претендует. Конечно же под него можно оптимизировать код.

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

На полном серьезе, если интересно, давайте сделаем же.

[RubaXa]

Понятно, ну удачи вам в «конкурсах».

[printf]

Спасибо, буду стараться разочаровать.

[w0den]

Очень интересный комментарий :)

[w0den]

Я отказался от участии в конкурсе из-за того что с такими правилами очень легко назначить победителем «нужного» человека, ибо организатор может менять правила (в этом случае бенчмарк) по мере необходимости. Это почти тоже самое как угадать число которое задумал человек, при этом он нигде не записал и никому не рассказывал какое именно число он задумал.

[tenshi]

Особенно веселит «специальный приз» за самое медленное решение на эвалах, которое сливает даже выполненным в функциональном стиле)
Эвалы дают +1 к скорости в микробенчмарках и -1 к поддерживаемости в реальных проектах.

[printf]

Специальная олимпиада, специальный приз.

(Меня тоже веселит. Почему бы и нет.)

[printf]

очень легко назначить победителем «нужного» человека

Это хитрый план, но зачем?

Допустим, я хочу отдать своему другу пару баксов. Я ведь могу их просто кинуть ему в пейпал, или попросить девочку в банке сделать перевод — решительно незачем устраивать такой-то спектакль с конкурсами, да еще подгонять бенчмарк под определенное решение.

Более того, затраченное на это время выйдет дороже, чем собственно приз.

[azproduction]

Набрать базу лояльных разработчиков :)

[printf]

А хорошая идея. В другой раз сделаю 25 призовых мест, пусть никто не уйдет обиженным.

[RubaXa]

А по мне так смешно получилось.
Чувак, можно было открыть бенчмарк и вам бы сразу указали на ошибку, да же больше, можно было и не менять бенчмарк, все бы сделали это бессмысленное кэширование и в итоге победила бы самая прооптимизированная функция, а не то что сейчас.

[printf]

Чувак, мы достигли результата, у нас все хорошо.

[RubaXa]

Так публикуйте результаты, не томите ;]

[printf]

В смысле, какие? Ребята, которые у нас теперь работают, сами напишут, если им этого захочется.

(Мы же вроде не скрывали, что работников таким способом ищем.)

[KlonD90]

А в чем проблема опубликовать ну и с выводами почему и как. Выводы должны быть неплохие — во всяком случае мне было бы интересно если бы кто-то до конца мне объяснил в чем весь цимес то как оно внутри на уровне C преобразовалось то.

[printf]

Мало времени на это, да и зачем кормить унылых троллей. Запостим второй конкурс, тогда и выводы первого подведем, одним махом. Или как получится, не знаю.