Задачка по физике

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

Lake Wenatchee State Park

Не знаю, что за девушка на третьем фото, но я тоже хочу просто сидеть и смотреть на озеро. Люблю это место. (Снято 6 Мая. Я продолжаю восстанавливать историческую правду.)

Bryce Canyon

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

Zebra Slot Canyon Trail

Тропа на Zebra Slot идет по руслу пересохшей речки. Но песчаник изрезан водными потоками. Впереди - висячий барьер для скота. Я таких раньше не видел.

Еще один забавный кадр из Devils Garden.

Devil's Garden

Странно, что во всех странах если что-нибудь необычное, так сразу "дьявольский сад".

В окрестностях Escalante, где мы стояли, есть такое место, напоминающее Arches.

Willis Creek Slot Canyon

Опять я давно ничего не писал. Постараюсь немного наверстать фотографиями.

Это фото сделано в марте, во время нашей весенней поездки по национальным паркам штата Utah.

Boston Public Library

Фото Ирины Толковой.

Итоги 2017 (личное и скучное)

Решил все-таки сформулировать, что произошло в этом году, в русле тематики блога. Но в будущем, я думаю, что подобный текст скорее подходит для "facebook close friends" группы. Так что присылайте friend requests: https://www.facebook.com/valeriy.tolkov.

Работа - все та же…

• …но уже не в своем офисе, а в team room: таков нынешний тренд. Хорошо, хоть, не прямо в проходе, как в некоторых других компаниях.
• Весной ухожу на part time. Буду ходить на работу 3 дня в неделю. Поработаю немного в этом режиме и начну не спеша смотреть на разные варианты.

Дома все, в общем, хорошо.

• Лена дописала книгу (http://www.springer.com/us/book/9783319732862) и начала преподавать физику в колледже.
• Ирина продолжает образование в Гарварде.
• Игорь работает и путешествует. Последняя его поездка была в Непал с восхождением на базовый лагерь Эвереста.

Мои поездки уже описаны здесь, в блоге, в основном.

• Очень понравилась поездка весной в Zion National Park и Bryce Canyon National Park.
  
• Летом посетили Бостон на восточном побережье, осмотрели Harvard и MIT, прокатились на машине на север вдоль восточного побережья до Новой Шотландии.
  
• В августе наблюдали полное затмение в Орегоне.
  
• И по-мелочи, нашли время на Ванкувер, Рейнир, Святую Елену.
  
• И наконец, традиционная зимняя Мауи (есть фотки на facebook).
  

Игрушки - ничего интересного.

• Обновил свой iPad до iPad-pro 10.5". Сначала попробовал большой 12" iPad, но потом сдал обратно: экран хороший, но большой держать в руках не удобно, а большой экран есть на десктопе. iPad-Pro стал практически основным устройством: на нем делаю все, кроме программирования.
  
• На работе всем дали большие 4K мониторы, в результате дома тоже обновил монитор до 4K, хотя мой Mac Mini 2012 его немного не тянет и вообще, я уже несколько раз зарекался покупать LG. Mac Mini обновить можно, но последний был в 2014, а нового пока нет и неизвестно когда будет.
  
• На работу купил наушники Sony h.ear: хорошо гасят внешний шум, но дешевле, чем Bose. Болтовню в комнате давить полностью технология еще не умеет, но давит ее достаточно хорошо до уровня неназойливости, особенно если включить какие-нибудь "10 hours of natural sounds" с You Tube.
  
• Камеру решил в этом году не менять. Full frame - дорого и громоздко. Не такой я фотограф, чтобы таскать эту тяжесть. Хотел взять Sony 6500, к которой подойдут объективы, но у меня еще Nex6 вполне работает. В принципе, я снимаю больше для собственной памяти, а это даже удобнее делать телефоном.
  

Софт и программирование - ничего особенно нового в практическом смысле.

• Кругом сплошной deep learning и нейронные сети, пошел в массы face recognition и все такое. Можно взять Open CV и сделать face recognition на Javascript в несколько строчек. Программирование вообще стало таким, собиранием perpetum mobile из абревиатур. Но практически, как меня не понимала Siri, так и не понимает. Никакой сингулярности пока не произошло и даже вообще пока не произошло ничего изменяющего хотя бы какую-нибудь одну мелкую привычку.
  
• Пытался читать про Azure API, что надо бы по работе, но не идет. Организм сопротивляется. Есть много технологий, которые я благополучно избежал или пережил. Микрософт их генерирует и выкидывает быстрее, чем у меня доходят руки. Хотелось бы и эту пережить.
  
• Вместо этого, почитал, наконец, про язык Rust. По описанию понравилось, хотя есть некоторые сомнения в удобстве практического использования. Давно хочется отходить от громоздкой искуственности конструкций С++, но я пока не уверен, что Rust - правильная альтернатива. Но есть в нем какая-то хакерская элегантность. Имя мне, правда, жутко не нравится и от "corrode" меня просто корродиткоробит.
  
• Со Свифтом, попробовал, но обнаружил, что Objective-C++ мне пока удобнее: всю логику делаю на привычном С++, и только тонкий уровень абстракции вокруг OS API делаю на Objective-C.
  
• Перешел на promises and async в node.js, неплохо получается.
  
• Visual Studio Code вполне пригоден как редактор, хотя дает на всех операциях какую-то небольшую неприятную задержку, типичную для web-apps. Наверное, можно привыкнуть.
  
• После попытки апгрейда домашнего десктопа с Maverick на High Sierra, который (апгрейд) застрял на середине, попытался откатить используя свежий time machine backup и после восстановления не нашел половину файлов. Слава богу, я использую Git для основных вещей, и смог снова все восстановить. Но time machine теперь очень не рекомендую. И вообще качество софта Apple как-то заметно упало последнее время. Правда, у Microsoft оно тоже не выросло.
  

Разное:

• В этом году стали больше ездить на велосипедах. В Сиэтле стало существенно лучше в этом смысле. Наконец-то по набережной стало можно и приятно проехать и прогуляться. В центре появились выделенные и отгороженные полосы. На новом мосту через озеро Вашингтон открылась велодорожка, поездка на велосипедах в центр Сиэтла стала нашей типичной прогулкой выходного дня.
  
• Поменяли дантиста. Новый ставит коронку за одно посещение. Обснимет зуб камерой со всех сторон, потом обточит его и снова обснимет, компьютер делает объемную модель, которая потом печатается на 3D принтере. Полтора часа визита - и коронка на зубе. Даже удивительно, что это реально работает.
  
• С удивлением открыл для себя англоязычный fanfiction. Удивительно как много люди пишут задаром, причем даже неплохо иногда. Тысячи страниц. Я вот эту страницу месяц собирался написать, и до сих пор не уверен, что это было нужно. А люди пишут и пишут…
  
• Иногда хочется снова взять и поехать куда-то еще. Выборы Трампа показали, что население здесь делится пополам, причем по разным измерениям, при этом одна половина не любит другую. Коменты к новостийным статьям в фейсбуке читать - опасно для психического здоровья, столько выливается агрессии и ненависти. Трамп периодически что-то там отменяет, к радости тех, кто хочет больше денег и прямо сейчас и плевать им на все остальное. Короче, такое депрессивное де-жа-вю, как и не уезжал никуда. Инстинкты у всех народов одинаковы…
  

Но в целом, все неплохо, если посмотреть на вышеперечисленное. Надеюсь в новом году будет лучше, чего и всем желаю.

Everest Base Camp

Давно я ничего здесь не писал. Надо снова с чего-то начать, проще всего с фотографии, а еще проще - с чужой. Эту фотку Игорь прислал из Непала.

tolkov.com is moved

The tolkov.com is now hosted by Amazon S3. I hope everything works as before.

Total Solar Eclipse

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

Конечно, комнату в городке в "zone of totality" снять не удалось даже за полгода до события. Пара комнат, что были доступны уже стоили порядка тысячи долларов за ночь. Мы сняли местечко под палатку на реке Колумбия в часе езды от зоны затмнения. Парк на берегу Dechutes River был приятен сам-по-себе.

В новостях сообщали о миллионе человек, которые приедут в зону. Затмнение должно было произойти около десяти утра, мы проснулись пол-пятого, наскоро в темноте выпили приготовленный с вечера кофе и поехали, надеясь успеть проехать до начала пробки. Мы поехали в город Антилопа, который находится в северной части полосы полного затмнения. Немного недоехав до города мы обнаружили удобную площадку на возвышенности, на которой уже стояло много машин и палаток. Похоже, многие стояли там с вечера. Мы подумали, что "the more the merrier" и встали там же. Народ стоял капитально, со штативами, телескопами и полными походными холодильниками.

Начало затмнения увидеть без специальных очков невозможно. Мы запаслись правильными очками заранее. Эти очки в картонных оправах продавали большими пачками, так что лишние раздавали на месте соседям и всем желающим. В очках видно, как луна начала заползать на диск солнца почти за час до наступления полного затмнения, но без очков никакой разницы не было видно. Так что мы сидели и ждали. Когда от солнца остался лишь узкий серп, визуально все еще ничего не было заметно, но мы почувствовали, что стало заметно холоднее. Солнце светило, но больше не пекло. Затем стало как-то странно темнеть. Казалось бы день, солнце высоко, блики, тени, но какие-то не яркие, приглушенные.

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

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

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

Mt. Rainier

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

Mount St. Helens

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



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

Halifax, Nova Scotia

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

Peggy's Cove

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

Memorial Day on Lake Wenatchee

Icicle River Gorge

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++;
    }
  }

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" была закрыта из за сильного течения воды, но эта, другая речка, вполне дает представления о игре света в изрезанном водой песчанике.