Комментарии 126
Вы сначала опубликуйте решение прошлой задачи thecodeil.com/
Оно уже у вас висит 3 года, а решение вы вывесить не удосуживаетесь.
Оно уже у вас висит 3 года, а решение вы вывесить не удосуживаетесь.
А она остается в силе. Это бесконечная вялотекущая задача, нам еще присылают решения, и специально обученная девочка их проверяет (очень медленно).
Именно поэтому теперь у конкурса есть срок окончания.
Именно поэтому теперь у конкурса есть срок окончания.
А у нее решения, формально говоря, нету.
Потому что твое видение «as good as you would expect a good libc to implement such functions» не совпадает с видением организаторов.
Хуже, я подозреваю, если аккуратно обернуть стандартные strcpy/strcat, решение не проканает.
И пробовать играть в эту телепатию неинтересно совсем, тк. итерация длится 2 месяца (?!!!) и в ответ приходит стандартная отписка.
Потому что твое видение «as good as you would expect a good libc to implement such functions» не совпадает с видением организаторов.
Хуже, я подозреваю, если аккуратно обернуть стандартные strcpy/strcat, решение не проканает.
И пробовать играть в эту телепатию неинтересно совсем, тк. итерация длится 2 месяца (?!!!) и в ответ приходит стандартная отписка.
На вот это решение спустя два месяца был получен ответ «Очень слабое решение, посмотрите на типичный список ошибок» — и ссылка на вот это!
Решение — 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;
}
Да, прошлая задача реально неудачная. Я сам на эту тему столько копий сломал.
Но так уж исторически сложилось.
В этот раз всё лучше: есть и способ валидации, и сроки окончания.
Но так уж исторически сложилось.
В этот раз всё лучше: есть и способ валидации, и сроки окончания.
Без кейсов тестирования — это совершенно бессмысленное соревнование.
Тесты в репозитории же.
Это юнит-тесты. А я про те тесты, которыми будет измеряться скорость.
Очевидно, что под разные кейсы использования можно оптимизировать код по-разному, т.е. оптимизировать одни операции в ущерб другим.
Очевидно, что под разные кейсы использования можно оптимизировать код по-разному, т.е. оптимизировать одни операции в ущерб другим.
В бенчмарке будут самые обычные тесты, из кода логирования и т.п. вещей.
Если их раскрыть, то появится возможность написать код, который очень быстро и хорошо проходит все тесты – и только их, т.е. ни в каком другом случае не работает. Формально это является решением.
На олимпиадах по программированию тоже никогда не открывают приемочные тесты, т.к. теряется всякий смысл.
Если их раскрыть, то появится возможность написать код, который очень быстро и хорошо проходит все тесты – и только их, т.е. ни в каком другом случае не работает. Формально это является решением.
На олимпиадах по программированию тоже никогда не открывают приемочные тесты, т.к. теряется всякий смысл.
На олимпиадах по программированию правильность измеряют, а не скорость.
Затачивать код под неизвестный кейс — бессмысленная затея.
Затачивать код под неизвестный кейс — бессмысленная затея.
Именно. Поэтому не надо затачивать, надо переделывать код, чтобы он в принципе работал быстрее. Как в настоящем проекте. В продакшене никаких тестов нет, там юзеры.
Вырожденных дурацких случаев вида "%d%d%d 250 тысяч раз" в финальном тесте не будет.
Мы ограничиваем снизу корректность, измеряем скорость.
Такая вот анти-олимпиада.
Вырожденных дурацких случаев вида "%d%d%d 250 тысяч раз" в финальном тесте не будет.
На олимпиадах по программированию правильность измеряют, а не скорость.На олимпиадах органичивают снизу скорость, измеряют корректность.
Мы ограничиваем снизу корректность, измеряем скорость.
Такая вот анти-олимпиада.
Основной вопрос — другой. Нужно знать какой вариант будет тестироваться:
а) "%d %m %h"( date ) * вызов этого 1000 раз
б) вызов 1000 раз "%d %m %h"( date ) с полным перезапуском
в) вызов 10 раз любого из этих кейсов.
Для всех этих трёх случаев принцип оптимизации разный.
Ещё там есть такой забавный параметр, как locale, который можно указывать для каждого случая.
Если эта функция будет действительно использоваться на продакшене, то было бы намного оптимальнее сразу поменять синтаксис и сделать
Все остальные варианты являются заранее не оптимальными бай дезайн.
а) "%d %m %h"( date ) * вызов этого 1000 раз
б) вызов 1000 раз "%d %m %h"( date ) с полным перезапуском
в) вызов 10 раз любого из этих кейсов.
Для всех этих трёх случаев принцип оптимизации разный.
Ещё там есть такой забавный параметр, как locale, который можно указывать для каждого случая.
Если эта функция будет действительно использоваться на продакшене, то было бы намного оптимальнее сразу поменять синтаксис и сделать
var format1 = dateFormatter(template, locale,options);
format1(date)//*1000 вызовов
Все остальные варианты являются заранее не оптимальными бай дезайн.
Да запросто, можно поменять. Хотя по большому счету разницы нет, оно может внутри оригинального вызова то же самое ведь делать.
Направление верное.
Направление верное.
Оно может кэшировать от template. Это потеря ln(O) на каждом вызове, но это мелочь. А вот когда приходит locale — всё меняется. Тут при кешировании сложность O, либо оно на самом деле использует этот переданный locale и опять же ln(O), потому я и пишу что генератор функции является оптимальным, а остальное порождает некоторый оверхэд.
del
ребят, как человек только поверхностно знакомый с Node.js, хотел бы спросить: а какие такие приемущества он предоставляет, что вы тритите своё время на оптимизацию его функций вместо того, чтобы писать на любом другом интерпретируемом языке (php, python, ruby)? многие из них транслируются в байт-код и имеют нечто наподобие JIT, что позволяет забыть об оптимизации работающего не кривого кода.
Во-первых, нод весьма низкоуровневый, в отличие от.
Во-вторых, нод принципиально заточен под клиент-сервер схему, а не «выполнить скрипт и умереть».
В-третьих, нод — событийно-ориентированный и неблокирующий, т.е. заставляет писать в асинхронных парадигмах, а это, как показывает практика, парадигма, в которой достигается максимальная производительноть (проблема 10К соединений).
В-четвёртых, нод/JS и так производительней абсолютного большинства скриптовых языков — сейчас идут напряженные баталии о том, можно ли от него добиться производительности статически типизированных компилируемых языков.
В-пятых, количество кода на NodeJS растёт просто экспоненциальными темпами, JS давно уже самый популярный язык на гитхабе.
Поэтому ваш вопрос нужно ставить иначе: а какие преимущества дают php/python/ruby, чтобы писать на них?
Во-вторых, нод принципиально заточен под клиент-сервер схему, а не «выполнить скрипт и умереть».
В-третьих, нод — событийно-ориентированный и неблокирующий, т.е. заставляет писать в асинхронных парадигмах, а это, как показывает практика, парадигма, в которой достигается максимальная производительноть (проблема 10К соединений).
В-четвёртых, нод/JS и так производительней абсолютного большинства скриптовых языков — сейчас идут напряженные баталии о том, можно ли от него добиться производительности статически типизированных компилируемых языков.
В-пятых, количество кода на NodeJS растёт просто экспоненциальными темпами, JS давно уже самый популярный язык на гитхабе.
Поэтому ваш вопрос нужно ставить иначе: а какие преимущества дают php/python/ruby, чтобы писать на них?
Про низкоуровневость расскажите поподробнее, очень любопытно послушать.
А чего рассказывать, стандартная библиотека Node.js практически как в Си.
Высокоуровневые примитивы появляются в библиотеках (например, connect).
Высокоуровневые примитивы появляются в библиотеках (например, connect).
Ну так какие отличия-то от Пайтона, ПХП, Руби?
Вы даже не представляете себе стандартную библиотеку Питона, правда?
В стандартной поставке Питона – целая куча структур данных, алгоритмов, поддержка сетевых протоколов, форматов файлов, разнообразного кодирования, в т.ч. поддержка записи аудиофайлов (!), UI тулкит (!), встроенная СУБД.
А в ноде – чтение-запись файлов (== потоков байт), простенький веб-сервер и биндинги к openssl.
В стандартной поставке Питона – целая куча структур данных, алгоритмов, поддержка сетевых протоколов, форматов файлов, разнообразного кодирования, в т.ч. поддержка записи аудиофайлов (!), UI тулкит (!), встроенная СУБД.
А в ноде – чтение-запись файлов (== потоков байт), простенький веб-сервер и биндинги к openssl.
Неправда, я на нём пять лет пишу. Наличие высокоуровневых вещей никак не противоречит наличию низкоуровневых. А нода просто не обросла нормальными библиотеками, очевидно, и только.
Да-да, и Си тоже вот как-то «не оброс».
Смеётесь что ли? Поищите к нему библиотеки, всё есть.
«Уровень» языка прежде всего определяется уровнем абстракции, которым приходится оперировать.
Ваш коммент заминусован потому, что, по вашей логике, Си — высокоуровневый язык, а это не так, несмотря на количество имеющихся библиотек.
Нод заставляет писать на максимально близком «к железу» уровне, насколько это вообще возможно без потери кроссплатформенности. Практически всё написано через бинарные буферы; модуль http заставляет работать со всеми кишками http, даже POST-данные нужно через Stream грузить; и тому подобное. Это не вопрос наличия библиотек — это вопрос того, какими структурами данных и операциями вам нужно манипулировать в «голом» языке.
Ваш коммент заминусован потому, что, по вашей логике, Си — высокоуровневый язык, а это не так, несмотря на количество имеющихся библиотек.
Нод заставляет писать на максимально близком «к железу» уровне, насколько это вообще возможно без потери кроссплатформенности. Практически всё написано через бинарные буферы; модуль http заставляет работать со всеми кишками http, даже POST-данные нужно через Stream грузить; и тому подобное. Это не вопрос наличия библиотек — это вопрос того, какими структурами данных и операциями вам нужно манипулировать в «голом» языке.
Нет, я не считаю Си высокоуровневым. Но я не считаю Джаваскрипт низкоуровневым и именно к этой мысли и я пытался подвести собеседника. На «голом» Пайтоне операции примерно те же, есть язык, а есть набор модулей к нему — это разные вещи, даже если распространяются вместе.
А мы не про джаваскрипт, а про нод.
Тогда давайте вернёмся к началу. Диалог такой получается:
— Как человек только поверхностно знакомый с Node.js, хотел бы спросить: а какие такие приемущества он предоставляет?
— Нод весьма низкоуровневый, в отличие от.
Тогда мне бы хотелось понять в чём тут преимущество. Так как я сделал какие-то свои выводы и принялся с ними спорить.
— Как человек только поверхностно знакомый с Node.js, хотел бы спросить: а какие такие приемущества он предоставляет?
— Нод весьма низкоуровневый, в отличие от.
Тогда мне бы хотелось понять в чём тут преимущество. Так как я сделал какие-то свои выводы и принялся с ними спорить.
Высокоуровневое хорошо ровно до того момента, пока оно покрывает все кейсы. Есть библиотеки, которые дают абстракцию над этим, но если надо, то в неё всегда можно залезть и переделать под свой кейс.
Преимущество в том, что **заставляет** писать код, заточенный под максимально эффективное взаимодействие с системой. В чём преимущество в контроле за памятью в C?
Конечно, не для всех это преимущество.
Конечно, не для всех это преимущество.
Нода на многих задачах изначально быстрее, чем php, python и (особенно) ruby.
Забыть про оптимизацию не позволяют масштабы проекта, увы.
Забыть про оптимизацию не позволяют масштабы проекта, увы.
Чтобы не быть голословным, киньте пруф сравнения с php 5.4.
Я действительно не понимаю в каком месте node уделывает php в производительности, киньте, плз, ссылку. Я не фанат php, я люблю scala. Мне просто интересны реальные тесты производительности, а гугл таких тестов не дает.
Можно потестировать самому. Можно погуглить.
Первый результат в гугле. По ссылке V8 уделывает по скорости пхп непонятно какой версии в среднем в 9 раз.
Первый результат в гугле. По ссылке V8 уделывает по скорости пхп непонятно какой версии в среднем в 9 раз.
Самое интересное в этом бенчмарке, что в нем не показано, какой код против какого тестируют. То есть получаем 9 попугаев в вакуме. Что-то здесь не так.
Ну приехали, там же прямо на этой странице ссылки на все исходники.
(Ссылки это синие такие буковки, в них мышкой кликают.)
(Ссылки это синие такие буковки, в них мышкой кликают.)
Спасибо, сразу не приметил.
Тем не менее цитата с первой страницы теста: «Measurement is highly specific». И дальше разъяснение, что тест не учитывает вообще никакой специфики языка и меряет лишь производительность игрушечной программы. Это также легко понять если посмотреть в исходники.
Теперь понятно, почему в условиях конкурса "«Эталонный» бенчмарк является восхитительной тайной."
Тем не менее цитата с первой страницы теста: «Measurement is highly specific». И дальше разъяснение, что тест не учитывает вообще никакой специфики языка и меряет лишь производительность игрушечной программы. Это также легко понять если посмотреть в исходники.
Теперь понятно, почему в условиях конкурса "«Эталонный» бенчмарк является восхитительной тайной."
И вообще почему все так стремятся уйти со статистически типизированных языков к динамически-типизированным?
Не спорю, на маленьких проектах динамическая типизация выглядит привлекательно. Но когда проект вырастает, и количество постоянно работающих над ним программистов становиться больше одного, то постоянно возникают проблемы — 'а что возвращает код написанный другим программистом?'.
Приходиться либо отвлекать соседа и спрашивать, либо самому тратить время и разбираться. А уж рефракторинг и изменение возвращаемых значений и вовсе превращается в головную боль.
Не спорю, на маленьких проектах динамическая типизация выглядит привлекательно. Но когда проект вырастает, и количество постоянно работающих над ним программистов становиться больше одного, то постоянно возникают проблемы — 'а что возвращает код написанный другим программистом?'.
Приходиться либо отвлекать соседа и спрашивать, либо самому тратить время и разбираться. А уж рефракторинг и изменение возвращаемых значений и вовсе превращается в головную боль.
Для решения этой проблемы существуют IDE и соглашение вести документацию.
Да как-то не особо с этим в IDE.
Вот в этом примере список доступных полей однозначен, однако же PhpStorm в code completion покажет список всех полей всех классов. Нерелевантный bar — в том числе.
Вот в этом примере список доступных полей однозначен, однако же PhpStorm в code completion покажет список всех полей всех классов. Нерелевантный bar — в том числе.
Скрытый текст
function f() {
return {
foo: "Lorem ipsum"
}
}
function g() {
return {
bar: 42
}
}
var
x = f();
x.| // ⇐ cursor here
Но ведь необходимость в комментировании — это признак плохого кода. Код должен быть читаем без всяких посторонних (часто неактуальных) комментариев.
Как большой поклонник js я был бы рад даже слабой типизации. Приятно было бы написать (count int, data obj) и даже не думать о проверках.
Ребята, ваш прошлый конкурс — бессовестнейшее разводилово. Чем отличается этот?
Вот список ребят, которые получили призы. Несколько человек остались у нас работать, могу познакомить.
А на обиженных традиционно воду возят.
А на обиженных традиционно воду возят.
Нет, вопрос не по списку ребят, которые «получили призы». Вопрос в том, чем тот конкурс отличается от этого?
Я был бы крайне признателен, если бы вы, или Рути, указали слабые стороны в решении, которое отправлено выше. В решении, которое настолько слабое, по словам Рути, что даже не нужно уточнять, в чем именно оно слабое — ведь это и так очевидно. Просто найдите хоть что-то, к чему можно прицепиться, что нарушало бы правила вашего же конкурса, для того, чтобы подтвердить свою позицию.
Я был бы крайне признателен, если бы вы, или Рути, указали слабые стороны в решении, которое отправлено выше. В решении, которое настолько слабое, по словам Рути, что даже не нужно уточнять, в чем именно оно слабое — ведь это и так очевидно. Просто найдите хоть что-то, к чему можно прицепиться, что нарушало бы правила вашего же конкурса, для того, чтобы подтвердить свою позицию.
Можно написать Рути и спросить. Адрес же есть.
Сделаем проще: я завтра спрошу у техдира и опубликую его ответ. Годится?
Отличается значительно: язык другой, задание другое, приемочные критерии объективные.
Есть также сходство: никто не заставляет в этом участвовать. Даже вас. Особенно вас. Мы вообще против насилия и за личностные свободы, что бы этот набор слов ни значил.
Сделаем проще: я завтра спрошу у техдира и опубликую его ответ. Годится?
Отличается значительно: язык другой, задание другое, приемочные критерии объективные.
Есть также сходство: никто не заставляет в этом участвовать. Даже вас. Особенно вас. Мы вообще против насилия и за личностные свободы, что бы этот набор слов ни значил.
Задача: разогнать оригинальную функцию strftime в 50 раз
Интересно, данный код вообще возможно ускорить в 50 раз? У вас уже есть пример того, как это сделать?
Почему не публикуете свою вторую задачу — сделать cujojs/when, самую быструю библиотеку Promise/A+, быстрее хотя бы в 5 раз?
Может немного не в тему, но тоже про оптимизацию скорости работы с датами.
Как-то вспомнилось…
Необходимо было сгенерировать карту сайта с количеством элементов около 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 секунд.
Как-то вспомнилось…
Необходимо было сгенерировать карту сайта с количеством элементов около 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 секунд.
Победит тот кто напишет на c модуль для javascript?
Стратегически, мне видится следующая оптимизация функции strftime, для некого входного сочетания форматеров (%x1, %x2 и т. д.) генерируется функция, которая потом вызывается каждый раз когда встретится такое же сочетание форматеров. Эта функция будет возвращать результат выражения, состоящего максимум из операций конкатенации и обращений к объекту локализационных параметров, плюс вычисления связанные с смещением зоны. Оверхед только при первом вызове strftime для нового сочетания, на генерацию такой функции, зато потом вызывается единственная функция. Мы сразу уходим от регулярного выражения, функции replace и последующих вызовов функций для каждого форматера
Собственно возникает вопрос тестирования скорости, может каждый раз будет исполняться холодный старт и компиляция функции под конкретный кейс даст только оверхэд.
В любом случае придется строить вспомогательную структуру, например дерево префиксов для групп сочетаний, или еще что-то, поэтому от холодного старта не уйти. Т.е. что-то необходимо построить на этапе препроцессорной обработки. А далее использовать эту структуру для обхода, с получением результата. Если никакой структуры строить заранее не придется, то тогда мне будет очень интересно посмотреть из чего выжмут производительность, буду учиться у победителей.
Вот, например, отказ от проверки всех RequiredDateMethods у данного объекта в методе quacksLikeDate (с учетом того, что данный метод внутри модуля используется только для различения даты и локали), ускоряет strftime примерно раза в два.
Таким образом, встает вопрос:
а действительно ли надо делать такую проверку или достаточно просто проверить, локаль это или не локаль?
Таким образом, встает вопрос:
а действительно ли надо делать такую проверку или достаточно просто проверить, локаль это или не локаль?
Мне одному кажется, что 500$ за решение этой задачи маловато?
printf, я может что-то не понял, но в 50 раз, это точно не ошибка?
Или может мы как-то по другому «разы» меряем?
Вот простой бенчмарк для
«Разогнать в 50 раз» — это значит получить ~30,000,000 ops/sec ?!
Можете написать, каким образом устроен ваш бенчамарк и что такое 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 раз?
Ну да.
Бенчмарк устроен примерно так же, а 50 раз это ориентировочная цифра. Она, конечно, зависит от машины, на которой это все выполняется, и от других вещей.
Бенчмарк устроен примерно так же, а 50 раз это ориентировочная цифра. Она, конечно, зависит от машины, на которой это все выполняется, и от других вещей.
Ну, вот, под ГуглоХромом я вчерась разогнал где-то раз в 7…
От машины будет зависеть только максимальное ops/sec, а вот разница между
new Date и strftime будет примерно такая же, так что даже в теории вашу функцию нельзя убыстрить больше чем в 10 раз, хотя и эта цифра утопия. Либо нужно приложить к условиям, как именно будут выводится эти «50 раз», ну и массив входных данных.Я полагаю, такая цифра возможна, если мы оперируем большим количеством данных в одной сессии, т.е. мы можем кэшировать результаты каких-то функций и таким образом значительно ускорить их выполнение по сравнению с оригинальной функцией. При этом на маленьких выборках фукция с кэшированием может работать хуже.
Если в теории что-то нельзя сделать, а на практике можно, значит, теория неверна.
Да и сделайте адекватную приемку результатов. Чтобы все могли видеть, кто, что и в каком виде выполнил\отправил.
С удовольствием бы потратил время, но отталкивают некоторые вещи:
1. Если никто так и не достигнет желаемого результата, что тогда?
2. Если будут решения с одинаковой производительностью(увеличенной >50 раз), что тогда?
3. Если будет код которые замедляет всё остальное приложение, что тогда?
С удовольствием бы потратил время, но отталкивают некоторые вещи:
1. Если никто так и не достигнет желаемого результата, что тогда?
2. Если будут решения с одинаковой производительностью(увеличенной >50 раз), что тогда?
3. Если будет код которые замедляет всё остальное приложение, что тогда?
1. Мы просто отсортируем все присланные решения по скорости.
2. Не знаю, разберемся по мере возникновения проблемы.
3. Какое остальное приложение?
2. Не знаю, разберемся по мере возникновения проблемы.
3. Какое остальное приложение?
Максимум выжал 21х без кэша — 3.3kk op/sec для
Буст в 50 раз даже ручным кодом не удалось получить для паттерна выше. Для получения 50x без кэша/тредов точно не обойтись.
Заводилось в 1 ядро: Node v0.10.28 @ V8 3.14.5.9.
%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.
Что такое 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)
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)
Короткий кэш из 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;
Дело явно не в оптимизации кода, у меня например пустой модуль возвращающий строку, отличается от 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)
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)
printf,
Скажите пожалуйста, если не секрет, многие ли решили задачу?
Скажите пожалуйста, если не секрет, многие ли решили задачу?
Я конечно не настоящий сварщик, но увеличить скорость более чем в 8 раз мне так и не удалось:
gist.github.com/RubaXa/4271cac9c0d39fc892c8
P.S. Наверно тут нужно использовать какую-то черную магию, которая позволила бы увеличить скорость самого js:
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)
Ну, особая магия тут не нужна — хватит и обычной :)
Вот что мне удалось (не обращаете внимание на количество операций в секунду, ибо ноут не сильно шустрый):
Это результат теста для:
Единственная проблема, что только для строки
Надеюсь, до завершения конкурса я найду время чтобы заниматься этим, так как задача действительно интересная. А насчёт конкурса, чего бы не говорили другие — кажется с ним всё в порядке.
Вот что мне удалось (не обращаете внимание на количество операций в секунду, ибо ноут не сильно шустрый):
>> 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"
Надеюсь, до завершения конкурса я найду время чтобы заниматься этим, так как задача действительно интересная. А насчёт конкурса, чего бы не говорили другие — кажется с ним всё в порядке.
Я вижу, что у вас не передается вторым параметром время, а значит вы берете его просто как
new Date, так что рискну предположить, у вас там кеширование. Ибо как видно из кода под спойлером, Native код не сильно то и быстр, каждый дополнительный вывозов Date-метода резко понижает производительность.То есть, Вы хотели сказать что
Или я неправильно Вас понял?
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
Или я неправильно Вас понял?
Чтобы всё было справедливо и понятно — printf, скажите пожалуйста, для следующего теста, новая функция всегда должна работать в 50 раз быстрее?
ps. Было бы замечательно, если бы Вы показали результаты этого бенчмарка для Вашей функции.
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. Было бы замечательно, если бы Вы показали результаты этого бенчмарка для Вашей функции.
Вы это, напишите, что всё надо писать на английском, ибо проверять это будет не русскоговорящий человек.
Не понятно требование реализовать в точности такой же интерфейс. Все эти однобуквенные сокращения просто невозможно запомнить — приходится безконца лазить в шпоргалки. Кроме того, передавать паттерн при каждом вызове — не удобно и несколько медленнее.
Такое апи было бы куда предпочтительнее:
var formatTime = $jin.date.formatter( 'Weekday, YYYY-MM-DD hh:mm' )
formatTime( new Date ) // Thursday, 2014-05-23 11:45
Не понятно требование реализовать в точности такой же интерфейс. Все эти однобуквенные сокращения просто невозможно запомнить — приходится безконца лазить в шпоргалки. Кроме того, передавать паттерн при каждом вызове — не удобно и несколько медленнее.
Такое апи было бы куда предпочтительнее:
var formatTime = $jin.date.formatter( 'Weekday, YYYY-MM-DD hh:mm' )
formatTime( new Date ) // Thursday, 2014-05-23 11:45
API: было выше.
Английский: верное замечание, как-то не пришло в голову указать язык – страница же вся на нем. Это не критично, надо будет – переведем.
Английский: верное замечание, как-то не пришло в голову указать язык – страница же вся на нем. Это не критично, надо будет – переведем.
И так, наконец-то объявлены результаты конкурса и победителем стал… сам бенчмарк :]
Получилось это следующим образом, в начале теста наполняется массив из 1000 уникальный дат, а дальше от теста к тесту бегают по нему, а это значит, что простым присваиванием результата форматирования в объект даты, позволит выиграть этот конкурс. И даже больше, если бы вы просто вначале оригинальной функции strftime написали:
то получили бы ускорение примерно в 150 раза, это почти в два раза быстрей «победителя».
Самое интересное, такого не ожидал никто (судя по коду), чего угодно, но не такого :] По этому я не поленился и сделал честный бенчмарк, чтобы выявить настоящего победителя. Честный тест состоит из суммы разгона функции на полностью уникальных данных и на 1000 timestamp.
В итоге шестерка победителей выглядит следующим образом:
Это те юзернеймы, которые занимались именно оптимизацией функции strftime. Из результатов легко заметить, что ни о каких 50 раз речи не идет, но это все равно крутейший результат, с чем я и поздравляю ребят.
github.com/RubaXa/challenge_strftime — тут можно посмотреть каждый тест по отдельности и результаты других участников.
В конце хотелось бы узнать мнение организаторов конкурса (printf) по этому поводу и почему выбран именно такой «тест»?
Получилось это следующим образом, в начале теста наполняется массив из 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) по этому поводу и почему выбран именно такой «тест»?
Мнение очень простое — можно сделать целый ворох бенчмарков, запустить их на куче различных конфигураций и получить очень разнообразные результаты.
Прямо сейчас, во время написания этого сообщения, я запустил предлагаемый «честный бенчмарк» — и получил совсем-совсем другую шестерку победителей: у меня вариант kuchumovn в random-тесте победил siranthony, например.
Наш тест вовсе не идеальный, никто и не претендует. Конечно же под него можно оптимизировать код.
По существу могу предложить только сотрудничество, т.е. давайте замутим вместо этой ерунды какой-то классный конкурс вместе, с правильными тестами и другими вещами. С меня деньги, призы и майки, вообще запросто.
На полном серьезе, если интересно, давайте сделаем же.
Прямо сейчас, во время написания этого сообщения, я запустил предлагаемый «честный бенчмарк» — и получил совсем-совсем другую шестерку победителей: у меня вариант kuchumovn в random-тесте победил siranthony, например.
Наш тест вовсе не идеальный, никто и не претендует. Конечно же под него можно оптимизировать код.
По существу могу предложить только сотрудничество, т.е. давайте замутим вместо этой ерунды какой-то классный конкурс вместе, с правильными тестами и другими вещами. С меня деньги, призы и майки, вообще запросто.
На полном серьезе, если интересно, давайте сделаем же.
Я отказался от участии в конкурсе из-за того что с такими правилами очень легко назначить победителем «нужного» человека, ибо организатор может менять правила (в этом случае бенчмарк) по мере необходимости. Это почти тоже самое как угадать число которое задумал человек, при этом он нигде не записал и никому не рассказывал какое именно число он задумал.
Особенно веселит «специальный приз» за самое медленное решение на эвалах, которое сливает даже выполненным в функциональном стиле)
Эвалы дают +1 к скорости в микробенчмарках и -1 к поддерживаемости в реальных проектах.
Эвалы дают +1 к скорости в микробенчмарках и -1 к поддерживаемости в реальных проектах.
очень легко назначить победителем «нужного» человекаЭто хитрый план, но зачем?
Допустим, я хочу отдать своему другу пару баксов. Я ведь могу их просто кинуть ему в пейпал, или попросить девочку в банке сделать перевод — решительно незачем устраивать такой-то спектакль с конкурсами, да еще подгонять бенчмарк под определенное решение.
Более того, затраченное на это время выйдет дороже, чем собственно приз.
Набрать базу лояльных разработчиков :)
А хорошая идея. В другой раз сделаю 25 призовых мест, пусть никто не уйдет обиженным.
А по мне так смешно получилось.
Чувак, можно было открыть бенчмарк и вам бы сразу указали на ошибку, да же больше, можно было и не менять бенчмарк, все бы сделали это бессмысленное кэширование и в итоге победила бы самая прооптимизированная функция, а не то что сейчас.
Чувак, можно было открыть бенчмарк и вам бы сразу указали на ошибку, да же больше, можно было и не менять бенчмарк, все бы сделали это бессмысленное кэширование и в итоге победила бы самая прооптимизированная функция, а не то что сейчас.
Чувак, мы достигли результата, у нас все хорошо.
Так публикуйте результаты, не томите ;]
В смысле, какие? Ребята, которые у нас теперь работают, сами напишут, если им этого захочется.
(Мы же вроде не скрывали, что работников таким способом ищем.)
(Мы же вроде не скрывали, что работников таким способом ищем.)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разгоняем JavaScript вместе (Внимание, конкурс!)