2017-08-08

Mt. Rainier



В субботу мы поехали на Rainier и прошли по Skyline Trail. Гора в тумане, который на самом деле не туман, а дым от горящих в Британской Колумбии лесов. Стоит очень сухая погода: дождя не было уже почти два месяца, что нетипично для нашего климата.

Mount St. Helens



В середине июля Игорь снова решил участвовать в популярном велопробеге Seattle to Portland (сокращенно "STP", 325km). А мы поехали его встречать на машине, с ночевкой и посещением горы St. Helens. Эта гора - действующий вулкан, который извергался в 1980г, что стало местной катастрофой и самым сильным вулканическим извержением в штатах. На youtube есть фильмы про катастрофу. Фотка сделана с Johnston Ridge, который назван в честь вулканолога David Johnston, которой погиб наблюдая за извержением.



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




Halifax, Nova Scotia



Еще одна занятная фотография из нашей поездки по Новой Шотландии.

2017-07-29

Peggy's Cove



Peggy's Cove - небольшой рыбацко-туристский городок в "Новой Шотландии". Мы немного попутешествовали по этой Канадской провинции в июле. И ниже панорама того же места.

2017-05-29

strlen

At work, we have an old codebase, originally written on Unix. While porting it to Windows someone's decided that Microsoft standard library is not good enough and replaced most of the functions with his own minimal implementations, mostly by copying relevant pieces from older projects he was working on. So we have a bare minimum of CRT, written in 90ths style. Which is good, in some way. It survived two decades and works fine, but recently we started thinking that maybe we should update some hot functions to improve performance. So, I've decided to research what benefit we can get from modern programming technics starting with the simplest one, with strlen.

Actually, strlen is usually an intrinsic, which means we can't find its implementation in the library's source code: compiler produces it instead. Which doesn't always mean its optimal. Anyway, we can still see what it performance look like and we can replace it if we need.

The traditional "strlen" K&R-style implementation used to be something like that:

int strlen(const char *s){
  uint l=0; while(*s++) l++; return l;
  }

Or, maybe this. It can be optimized into "repnz scanb" instruction. Which made a difference on older processors.

int strlen(const char *s){
  const char *s0=s; while(*s) s++; return s-s0;
  }

With modern processors, there are two choices. We can use special SSE instructions, coding them on assembler or using compiler extensions. If we want to stay in C/C++ world, we can process 8 bytes at once by using 64-bit arithmetic and logical instructions. We can fetch 8 bytes as 64-bit word, then somehow determine if the word contains a zero byte. If it does not, we can increment length by 8 and jump to the next 8 bytes. If it does, we need to find the zero byte inside that word. The processing of the last word is not that performance-critical, its happens just once per string.

I know there are implementations (like GCC GNU library), but I like to reinvent a bicycle, so I wrote it myself for a bit of fun, relying on compiler to optimize trivialities:

int strlen4(const char *s){
  const uint64 *p=(const uint64 *)s; uint c=0;
  for(;;){
    const uint64 m=0x8080808080808080ull;
    const uint64 x=(((*p&~m)+~m)|*p)&m^m;
    if(x){
      s=(const char *)p; while(*s) s++; return c+(s-(const char *)p);
      }
    c+=8; p++;
    }
  }

Explanation:
  1. ~m is 0x07f7f7f7f7f7f7f7full by the way, and 'full' is a coincidence
  2. *p&~m // zeroing 8th bit of every byte
  3. (*p&~m)+~m // arithmetic addition will overflow to 8th bit when an only when the value on step 1 is non-zero, and it never overflow to the next byte
  4. ((*p&~m)+~m)|*p) // or-ing with original word will set 8th bit to one when 8th bit of *p is non-zero, and it also never overflow
  5. ((*p&~m)+~m)|*p)&m // selecting only 8th bits of every byte, which would be 1 when byte of *p is non-zero and 0 when it zero
  6. ((*p&~m)+~m)|*p)&m^m // inverting that bits, so it will have 1 for zero byte and 0 for non-zero
  7. now if entire word is 0, that means we don't have zero bytes

Finding a non-zero bit in 64-bit word can also be a little of a fun play, and I'll show some examples below. Also, the Intel SSE2 has instructions to do all that by one single command. SSE4 is also can be used, but I saw posts, explaining that SSE2 implementation is faster, so I've decided to skip SSE4 for now.

Let's go to tests. I wrote 9 variants of strlen (sources at the end of this post):

  • 0: no strlen is called, but all other test code is running -- to determine the baseline.
  • 1: calling just regular built-in "strlen"
  • 2-3: simple byte-per-byte implementations
  • 4-7: algorithm described above with different code determining the length of the last word, where methods 6-7 don't use conditional ifs
  • 8: using SSE2 intrinsics

Each of methods computes length of strings from 0 to 64. That is repeated 100000 times and time is reported in milliseconds. Every test is repeated 8 times using 8 different alignments of original strings.

Note, that higher bar means worse performance. Groups are for different variants, and inside each group we can see results for different alignments.

First run was on my home mac-mini machine (2.3 GHz Intel Core i7, Maverick):


We can see, that per-byte methods 2,3 are the worst, methods 1, 4, 5, 8 has almost identical performance. Which is a surprise, I thought that SSE2 will be better, it runs 128bit at once, not 64. Also, alignment of strings doesn't seems to matter, which is another surprise.

And the second is on my travel macbook (Processor 1.1 GHz Intel Core M, Sierra):


Below is a result of running test on Windows, with our project compiler and library, by two machines: a newer one (Intel Xeon CPU E5-1650 v3 @ 3.50GHz; Windows Server 2016, 64 bit) and an older one (Intel Core i7 CPU 920 @ 2.67Ghz; Windows Server 2008R2, 64 bit). Also I didn't run SSE2 test on them.



So, the built-in and per-byte tests are the worst. The older machine, the less that difference.

Also, I run the test with 32-bit compiler and the results are similar.



So, the morale is that per-byte is bad and 64-bit C++ is as good as SSE2.

Here is the code:
int _strlen1(const char *s){
  return strlen(s);
  }

int _strlen2(const char *s){
  const char *s0=s; while(*s) s++; return s-s0;
  }

int _strlen3(const char *s){
  uint l=0; while(*s){ s++; l++; } return l;
  }

int _strlen4(const char *s){
  const uint64 *p=(const uint64 *)s; uint c=0;
  for(;;){
    const uint64 m=0x8080808080808080ull;
    const uint64 x=(((*p&~m)+~m)|*p)&m^m;
    if(x){
      s=(const char *)p; while(*s) s++; return c+(s-(const char *)p);
      }
    c+=8; p++;
    }
  }

int _strlen5(const char *s){
  const uint64 *p=(const uint64 *)s; uint c=0;
  for(;;){
    const uint64 m=0x8080808080808080ull;
    uint64 x=(((*p&~m)+~m)|*p)&m^m;
    if(x) return x&0x00000000ffffffffull ?
                (x&0x000000000000ffffull ? 
                (x&0x00000000000000ffull ? c : c+1) : 
                (x&0x0000000000ff0000ull ? c+2 : c+3)) :
                (x&0x0000ffff00000000ull ? 
                (x&0x000000ff00000000ull ? c+4 : c+5) : 
                (x&0x00ff000000000000ull ? c+6 : c+7));
    c+=8; p++;
    }
  }

int _strlen6(const char *s){
  const uint64 *p=(const uint64 *)s; uint c=0;
  for(;;){
    const uint64 m=0x8080808080808080ull;
    const uint64 x=(((*p&~m)+~m)|*p)&m^m;
    if(x){
      const uint64 y=(x|(x<<8)|(x<<16)|(x<<24)|(x<<32)|(x<<40)|(x<<48)|(x<<56))^m;
      const uint64 z=y+(y>>8), u=z+(z>>16), l=u+(u>>32);
      return c+((l>>7)&0xf);
      }
    c+=8; p++;
    }
  }

int _strlen7(const char *s){
  const uint64 *p=(const uint64 *)s; uint c=0;
  for(;;){
    const uint64 m=0x8080808080808080ull;
    const uint64 x=(((*p&~m)+~m)|*p)&m^m;
    if(x){
      const uint64 y=(x|(x<<8)|(x<<16)|(x<<24)|(x<<32)|(x<<40)|(x<<48)|(x<<56))^m;
      const uint64 l=y+(y>>8)+(y>>16)+(y>>24)+(y>>32)+(y>>40)+(y>>48)+(y>>56);
      return c+((l>>7)&0xf);
      }
    c+=8; p++;
    }
  }

int _strlen8(const char *s){
  const __m128i z = _mm_setzero_si128();
  const __m128i* p = (const __m128i*)s;
  for(;;){
    __m128i xmm = _mm_loadu_si128(p);
    const uint mask = _mm_movemask_epi8(_mm_cmpeq_epi8(xmm,z));
    if(mask!=0) return ((const char*)p)-s+(ffs(mask)-1);
    p++;
    }
  }

2017-04-04

Zion National Park




Как-то сама собой сложилась традиция ездить в весенние каникулы в разные каньоны. В это время в более северных национальных парках еще лежит снег и парки наполовину закрыты. А весной хочется, чтобы было не только красиво, но и тепло. В позапрошлогодние каникулы мы ездили на Grand Canyon, в прошлом году - в Arches, и в этом году - в Zion National Park и в Bryce Canyon National Park, который всего в двух часах езды от Zion.

Удобнее всего было взять самолет до Las Vegas, и поехать в Zion на машине. При этом за три часа пути проезжаешь из штата Nevada через Arizona в Utah.

Занятно, как рядом мирно сосуществуют штат Nevada, где официально разрешены казино и проституция, и Utah, где живут мормоны, которые даже кофе не пьют.

Las Vegas мне не нравится, поэтому вернемся в Zion. Парк, начинается в уютном городочке Springdale и его доступная территория помещается в одном небольшом каньоне, прорезанного речкой, текущей с верхнего плоского плато в нижнее. По нижней части парка ходит бесплатный автобус, в верхнюю надо ехать самому на машине через тоннель, или взбираться пешком по одной из троп.

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


Нам очень понравилось побродить по сухому руслу сезонной речки, которая прорезала узкий канал в скале. К сожалению другая фото-достопримечательность парка, "Narrows" была закрыта из за сильного течения воды, но эта, другая речка, вполне дает представления о игре света в изрезанном водой песчанике.

2017-03-28

Bryce Canyon






Bryce Canyon - волшебное место, рай для фотографа. Или ад, если пытаться снять что-то никем не снятое. На панораме глюкнула матрица на артефактах, но каньон получился хорошо. Удивительно, как природа иногда вдруг генерирует сложность из ничего, посреди однообразной равнины. Так, наверное, образовалась наша вселенная, в уголочке, из ничего, посреди бескрайней пустоты.

2017-03-01

Цвет моря




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

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