конкурс по си

Сделал для себя маленькое наблюдение. И ещё раз убедился, что в библиотечных функциях сила.

Тоже написал FSM (wipeout) — там всего два прохода. Один раз в верх с затиранием всего ненужного. И коллапсирование пробелов, тоже за один проход. Никаких сторонних функций, возвтаров, поисков днины и т.д. А получилось медленней и запутанней, чем с использованием strchr, strstr и memmove. (cutout)

там просто смещение поправить надо, забыл про него, но в принципе я все-равно уже по другому сделал:

void undebug_wota(char *s) {
    char* p = s;
    for( ; *p && ( p = strchrnul( s, ' ' ) ) ; s = p + 1 ) {
        if( p - s == 5 && ( *((long*)s) & 0x000000FFFFFFFFFF ) == 0x6775626564 )
            memset( s, ' ', 5 );
    }
}

по идее это и будет самым коротким, корректным и быстрым решением

У нас теперь новый фаворит — wota

wota содержит неустранимую ошибку. Она(функция) быстрая, но мёртвая :)

конкурс по си (комментарий)

и что ?

«суслика видишь? нет..а он там есть» - это про ошибку, она никуда не делась

это про ошибку, она никуда не делась

какую именно ошибку?

если это про LE, BE - чистой воды придирка, т.к. разруливается дефайнами, а BE надо еще поискать

какую именно ошибку?

сегфолт вне зависимости от endianes

Беда только в том, что strchrnul — это чистый GNU-сизм. Эта функция есть только в Linux.

Обернул твой pull-request так, что для линукса собирается этот новый вариант, а для всех остальных платформ старый.

сегфолт вне зависимости от endianes

ну есть такая вероятность, да :) но очень небольшая, но раз такие зануды - сейчас уберу long

*((long*)s) вычитывает 8 байт, ты гарантируешь наличие в буфере 6 из них, остальные 2 берутся из запределья (в 99.99% они даже доступны на чтение); ошибка потенциально приводит к сложноуловимому сегфолту.

да это и так очевидно, я уже написал выше

на всякий случай - в рабочем коде я напишу strncmp, возьму int32_t а не int, не буду кастить char* в int* и т.д., но тут сказали, что это соревнование на скорость - потому и используются не всегда корректные приемы, тот же strchrnul я никогда раньше не использовал, да и «debug» не захардкоживал бы прямо в функции

П.С. ну и ты свой вариант предложи

void undebug_wota(char *s) {
    char *p = s;
    for (; *p; s = p + 1) {
        p = strchrnul(s, ' ');
        if (p - s == 5 && *((int*)s) == 0x75626564 && s[4]=='g')
            memset(s, ' ', 5);
    }
}

мой текущий вариант

Судя по треду на ЛОРе очень мало хороших программистов.

Судя по треду на ЛОРе очень мало хороших программистов.

еще забавнее, что самые быстрые варианты у толстотроллей, вот только твоего пока еще не хватает ;)

Ну у меня еще одна полуготовая версия есть, посмотрим как отработает, правда раньше ночи довести её до ума не смогу.

П.С. ну и ты свой вариант предложи

«незахардкоженный» :-) к тому-же что-то сходное уже было, поэтому не предложен ранее

inline void
tap_sp(char *r,int len,char *s) {
	char *p;
	#define NEXTWORD(v) for(s=v;*s && *s!=' ';) s++; while(*s==' ') s++
	if (strncmp(r,s,len)==0) {
		p=s+len;
		if (*p==0) {
			*s=0;
			return;
		} else if(*p==' ') {
			memset(s,' ',len);
			NEXTWORD(p+1);
		} else {
			NEXTWORD(p);
		}
	} else {
		NEXTWORD(s);
	}
#if defined(NO_STRSTR)
	while(*s) {
		if (strncmp(r,s,len)!=0) {
			NEXTWORD(s+1);
			continue;
		}
#else
	while((s=strstr(s,r))!=NULL) {
#endif
		p=s+len;
		if (*p==0) {
			*(s-1)=0;
			break;
		} else if (*p==' ') {
			memset(s,' ',len);
		}
		NEXTWORD(p);
	}
}
char *tap_sp_wrapper(char *r,char *s) {
	tap_sp(r,strlen(r),s);
	return s;
}
char *tap_sp_undebug(char *s) {
	tap_sp("debug",5,s);
}

по идее если хардкодить «debug» и не отказываться от мысли таскать и сравнивать данные через uint16/32, нужно отработать особые случае в начале строки, а дальше чтобы не переступить границу буфера, сравнивать не то что следует за ' ', а то что перед ним. Но субботняя лень :-)

мой текущий вариант

contest можно закрыть :-)

судя по лекциям Степанова очень мало хороших программистов в целом на земляшке.

звучить как самооправдание ,

всёж

хороший программист это некоторое гармоничное сочетание производительности понятности и робастости и много чего ещё.

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

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

код, который «откатился до агрегатноинтового», отличается от предыдущих (и «кода царя») более эффективным алгоритмом, в частности у меня не ищется каждый раз «debug» после пробела и нет проверки на завершающие \0 или ' '

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

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

ты его победил на его територии - т.е унизил ....

O_O

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

и я не считаю «полными синонимами лучшесть и производительность», но хотелось бы, чтоб «некоторые» показали более KISS решение чем мое, то, что ты писал раньше - нечитабельное нечто

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

Причем и этот пациент когда-то кукарекал на меня за то, что я захожу за края строки.

Финалный рейтинг (плюс-минус лапоть — от раза до раза замеренное время чуть-чуть плавает).

Имхо, лучше считать не среднее, а минимум, тогда результат получается стабильнее.

Если что — Debian/amd64. Вроде у valgrind'а какие-то проблемы с 64 бита.

Debian/i686-bigmem, может поэтому у меня работало. :) Он выдал, что многие функции читают за пределами строки, но то не важно, а важно то, что три функции (cut, cut2 и str_drop_str) ПИШУТ за пределы строки, вот какая-то из них портила хип.

Кстати, я смотрю, подключились и заточенные под «debug» варианты. Тогда вот вам:

char *anon_wipedebug(char *where, char *unused)
{
    char *p = where-1;
    do {
        ++p;
        if (*(int*)p == 'ubed' && (*(int*)(p+2)==' gub' || *(int*)(p+2)=='\0gub'))
            *(int*)p = '    ', p[4] = ' ', p += 5;
    } while (p = strchr(p, ' '));
    return where;
}

Не знаю, как будет на 64-битной, но на моей 32-битной обходит всех.

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

унизил не всмысле ты чуствуеш своё превосходство , а то , чем он(царь) обосновывал свою лучшесть окружающих оказалось им овладенно хуже чем тобой , при том козырят байтолюбстом в терминальной стадии с его _strcmp с прошитой иглой и использованием сокращённого логического и как фильтра начал он , а ты показал истинные алгоритмические трюки интерпретирую нужные 40(48) бит то как часть последовательности символов то как широкое целое.

про KISS:

о котором из своих ты говориш говоря

более KISS решение чем мое

?

это хорошо что переходы(continue) вниз по коду ты считаеш нечитабельным нечто , а вложеность if во вложеный if во вложеный if для тебя эталон ясности.

мой текущий вариант

К слову, в ядре нет strchrnul(). Но вариант красивый.

о котором из своих ты говориш

оба, первый:

int l = strlen(w);
char *p = s;

// Ищем слово в строке
while ((p = strstr(p, w))) {
    // Если слово слева и справа закончено
    if ((p == s || isspace(p[-1])) && (!p[l] || isspace(p[l])))
        // Затираем его
        memset(p, ' ', l);

    // Пропускаем слово, чтоб искать сразу после него
    p += l;
}

второй (чуть отформатил для комментариев)

char *p = s;
    
// Пока не дошли до конца строки
while( *p ) {
    // Ищем разделитель после текущей позиции
    p = strchrnul(s, ' ');
        
    // Между текущей позицией и разделителем слово debug
    if (p - s == 5 && *((int*)s) == 0x75626564 && s[4]=='g')
        // Затираем его
        memset(s, ' ', 5);

    // Переносим текущую позицию сразу за разделитель
    s = p + 1
}

а теперь опиши свой код построчно

    если игла пуста возвращаем исходную строку.
    полагаем N длиной иглы.
    в цикле
        вычленяем следующий промежуток между разрывами // разрыв это либо начало либо пробел либо конец.//слово есть между разрывами
        если длина слова не есть N следующая итерация.
        если слово не есть игла следующая итерация.
        заполняем слово пробелами.
    завершитель_цикла-левый разрыв есть конец.

идём по строке вычленяя «слова»

идём по строке вычленяя «слова»

это описание алгоритма, а не кода, и да - алгоритм вполне очевиден и прост, тут не спорю, а вот код - другое дело, «r - ++l != n» в условии, функция nxt, которая сходу делает инкремент, и для которой ты выписал «char *l = src - 1» - такие вещи затрудняют разбор кода

вообщет начальным декрементом я свёл все случаи к одному l и r это ограничители(разрывы) nxt по сути итератор на входе разрыв на выходе следующий разрыв.

конкурс по си (комментарий)

вообщет начальным декрементом я свёл все случаи к одному l и r это ограничители(разрывы) nxt по сути итератор на входе разрыв на выходе следующий разрыв.

да все там понятно, что ты хотел, но читать твой код не очень приятно, так как надо бегать глазами в вообще другую функцию, и если у меня, например, только один while + один if, без всяких break и continue, то у тебя два вложенных while, два continue, которые обрывают тело цикла, две функции, два портсигара и два несвязанных между собой места для перемещения по строке

выделение nxt в отдельную функцию это чисто личное предпочтение , можно было и в коде оставить.

хз почему я давно уже предпочитаю

...
if(!some1)contunie;
....1
if(!some2)continue;
main_body_of_loop
}

вместо

...
if(some1){
        ....1
        if(some2){
               main_body_of_loop
        } 
}
}

в данном случае так как нету промежуточных бойлерплейтов можно и было

одним условием (которое почти твоё (тока я всёж предпочитаю на этом уровни неразличать разделители)) и очисткой если условие успешно.

однако повторюсь

я предпочитаю условные continue вместо вложенности блоков.

раз пошла борьба с битами за такты ;-)

char *undebugit2(char *s) {
	char *ret;
	uint64_t the_debug=0x2064656275672000ULL;
	uint64_t acc=0x2000;
	ret=s;

	#define ONESHIFT if (*s) acc=(acc|*s++)<<8; else return ret;
	ONESHIFT;
	ONESHIFT;
	ONESHIFT;
	ONESHIFT;
	ONESHIFT;
	#undef ONESHIFT

	if(*s) {
		acc=(acc|*s)<<8;
		if (acc==the_debug) ret=s+1; 
		s++;
	} else goto FINAL;
	if(*s) {
		acc=(acc|*s)<<8;
		if (acc==the_debug) ret=s+1;
		s++;
	} else goto FINAL;
	// 7 bytes ready in acc*/
	while(*s) {
		acc=(acc|*s)<<8;
		if (acc==the_debug) memset(s-5,' ',5);//<-- optimize possible
		s++;
	}
FINAL:
	acc=(acc|' ')<<8;
	if (acc==the_debug) s[-5]=0;
	return ret;
}

«debug debugfs debug debug=1 systemd.debug debug» не прошло, а по скорости - сразу после варианта puzan'а

«debug debugfs debug debug=1 systemd.debug debug»

 input=«debug debugfs debug debug=1 systemd.debug debug»
result=«debugfs       debug=1 systemd.debug »

это из-за лишнего пробела в конце не прошло ?? :-)

то я ошибся, не использовал возвращенное значение

а по скорости..

а чтоб реально мерять по скорости - буфер в котором производятся замены должен быть большим (~несколько К или даже десятков К), а пока в основном измеряется насколько сильно в тесте ломаются кеши при входе в измеряемую функцию и как долго она инициализуется:)

напиши плз, если будешь прогонять у себя (особенно интересно если на linux), а то у тебя другие результаты получаются.

И это извини за опять поломанные отступы, я не успел перепослать пул.

http://qnikst.github.io/random/2014-04-06-lorcontest.html

вот такая штука получилась у меня на компе, извините, чьи решения не добавил. Могу запушить програмку, которй генерировал в репозиторий, но это haskell, так же в абсолютном времени есть overhead на выбов ffi.

Ещё одна ошибка, указатель на int* обязан быть выравненным по размеру sizeof(int) если вы собираетесь его разыменовывать и писать портабельный код.

Ещё одна ошибка, указатель на int* обязан быть выравненным по размеру sizeof(int) если вы собираетесь его разыменовывать и писать портабельный код.

да, я выше уже писал, что в рабочем коде не использовал бы int*

на моем железе:

Gros Relults
----

name             | func name        | passed           | gros time    | slower      
---              | ---              | ---              | ---          | ---         
wota             | remove_word      | ***************** |    240.89 ms |      8.15 % 
wota             | undebug_wota     | ****** *****   *  |    222.73 ms |      0.00 % 
qnikst           | undebugq uspace  | * *************** |    329.35 ms |     47.87 % 
qnikst           | undebugq2        | ***************** |    326.51 ms |     46.59 % 
qnikst           | undebugq3        | ***************** |    300.55 ms |     34.94 % 
qnikst           | undebugq         | * *************** |    340.37 ms |     52.82 % 
Carb             | debugdel         | * **** *****   *  |    249.08 ms |     11.83 % 

П.С. обновил remove_word, чтоб был побыстрее, т.к. undebug удаляет только debug и потому теперь не все проходит

Круто

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

кстати ещё что у меня удивляет, у меня undebug uspace обыгрывает undebugq2 и undebugq3, у всех остальных - наоборот...

это на gcc-4.6 и glibc-2.19 и hardened системе, щас ещё 4.8 попробую, но почему так я не понимаю..

это на gcc-4.6 и glibc-2.19 и hardened системе, щас ещё 4.8 попробую, но почему так я не понимаю..

я проверял на gcc-4.8.2, glibc-2.19, ubuntu 14.04, вот результат с clang-3.5 из транка:

Gros Relults
----

name             | func name        | passed           | gros time    | slower      
---              | ---              | ---              | ---          | ---         
wota             | remove_word      | ***************** |    263.53 ms |     13.85 % 
wota             | undebug_wota     | ****** *****   *  |    231.47 ms |      0.00 % 
qnikst           | undebugq uspace  | * *************** |    367.85 ms |     58.92 % 
qnikst           | undebugq2        | ***************** |    357.63 ms |     54.50 % 
qnikst           | undebugq3        | ***************** |    345.85 ms |     49.41 % 
qnikst           | undebugq         | * *************** |    368.42 ms |     59.16 % 
Carb             | debugdel         | * **** *****   *  |    277.46 ms |     19.87 %