Показаны сообщения с ярлыком нет покоя ебанутым. Показать все сообщения
Показаны сообщения с ярлыком нет покоя ебанутым. Показать все сообщения

14 июня 2021 г.

Cores that don't count: "тихие" производственные дефекты процессоров

TL;DR: Инженеры гугла утверждают, что примерно 0.1% современных процессоров содержат дефекты, ускользнувшие от техконтроля производителя, из-за чего некоторые инструкции на таких процессорах втихую дают неправильный результат. Вероятно, доля таких производственных дефектов будет расти. Вероятно, пора отвыкать думать о процессоре как об идеальном вычислителе, и искать способы создавать такие программные системы, которые обнаруживают и компенсируют ошибки CPU.

В твиттере проскочил очень интересный доклад Питера Хошчилда (Peter H. Hochschild) из гугл на конференции HotOS 20211

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

24 июля 2020 г.

Queueing theory for fun and practice (#1): square root staffing, Little's law

На 28-ом этаже центра разработки крупного инвестиционного банка есть 8 туалетных кабинок для людей, идентифицирующих себя с мужским гендером. Работающий в центре высокофункциональный аутист Иннокентий подсчитал, что когда он заходит в туалет, в среднем 5 из 8 кабинок уже заняты.

Сколько человеко-часов в день сотрудники офиса спускают в унитаз?

"Теория массового обслуживания для сантехников" (неизданное)

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

Материалы, которые мне попадались по теории массового обслуживания, распадаются на две категории: ТМО как раздел математики (теории вероятности), и ТМО как раздел бизнес-управления, менеджмента производства/обслуживания (operations research).

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

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

12 июня 2019 г.

Waiting time paradox #4: aftermath

(продолжение серии про парадокс времени ожидания)

…Мне кажется, это поразительный эффект: добавка sleep(5) в цикл обработки задач может уменьшать среднее время обработки. Даже после того, как я уже разобрался с этим эффектом на примере автобусной остановки, я все еще не мог поверить, что такой же эффект будет и в системе с очередью. И, несмотря на все формулы, разобранные примеры и симуляции, на интуитивном уровне я все еще ощущаю это как какой-то трюк. Это и поразительно: хотя логически я все понимаю, могу объяснить, и симуляцию написать, и картинку нарисовать – но моя интуиция все равно отказывается воспринимать это как очевидное.

И ведь происходит все в очень обыденной системе, с которой мы регулярно сталкиваемся в жизни. В математике есть множество выносящих мозг результатов, но многие из них выносят мозг просто потому, что относятся к системам, для которых в повседневной жизни нет аналогов. Парадокс Банаха-Тарского гораздо круче парадокса времен ожидания – но кто из нас в жизни сталкивается с разрезанием сферы на не-измеримые куски? Сама постановка задачи уже далеко выходит за рамки повседневного опыта и бытовой интуиции – не удивительно, что результат получается не интуитивный. Но очередь в Сбербанк, и кассир, который делает между клиентами минутную паузу, а иногда выбегает перекурить на 5 минут, а иногда попить чай на 15 – это обыденная ситуация. И оказывается, что в этой обыденной ситуации скрыто такое нетривиальное поведение!

8 октября 2016 г.

Скаляризация Map.get(new CompositeKey(key1, key2, ...))

Один из самых интересных примеров из моего последнего доклада на jug-ekb (на JPoint этот пример не влез) это скаляризация композитных ключей в поиске по словарю:
final Map<CompositeKey, V> map = ...;

...
    final CompositeKey key = new CompositeKey( key1, key2, ... );
    final V value = map.get( key );
...
Это весьма частый паттерн: нам нужно отображение вида [key1, key2, key3...] -> value. Наиболее простой и очевидный способ это сделать: как раз таки использовать композитный ключ (кортеж из ключей). Решение отличное по всем показателям, кроме одного: для каждого поиска в словаре придется создавать новый объект.

22 февраля 2016 г.

Tricky scalar replacement

...Однако, насяльника, код сильно сложный, синтаксический дерево большой, корень толстый, ссылка туда гоняй, сюда гоняй, одну присвояй, другую присовояй, моя не понимать...
Допустим, у нас есть класс Vector2D, типа такого:
public static final class Vector2D {
 private double x;
 private double y;

 public Vector2D( final double x,
                  final double y ) {
  this.x = x;
  this.y = y;
 }

 public Vector2D add( final Vector2D other ) {
  return new Vector2D(
    x + other.x,
    y + other.y
  );
 }

 public void addAccumulate( final Vector2D other ) {
  x = x + other.x;
  y = y + other.y;
 }

 public double dot( final Vector2D other ) {
  return x * other.x + y * other.y;
 }

 public double length() {
  return Math.sqrt( this.dot( this ) );
 }
}
(Конкретные детали не важны, нужен класс без сложной логики и коллекций внутри)

20 сентября 2015 г.

Немного тервера, или зачем нужны хартбиты


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

4 февраля 2014 г.

How fast the logger could be?

В начале декабря у нас тут случилась своя маленькая и уютненькая внутренняя конференция, на которой я рассказывал про быстрое логгирование. Поскольку конференция внутренняя, часть информации под NDA, так что просто выложить презентацию я не могу, но общие моменты попробую описать.

Задача взялась вполне себе из практики: есть приложение, которое зарабатывает бабло наносит пользу человечеству. У этого приложения есть legacy-версия, которая уж сколько-то лет в работе, и есть новая, с 0 переписанная (в основном мной) версия, которая сейчас готовится ее сменить на боевом посту. Разумеется, возникает масса вопросов вида "а почему вот в новой версии у этой транзакции результат чуть не такой, как в старой?". И приходится много времени шароебиться по логам, выясняя, как и что происходило. И, конечно, регулярно думаешь, что вот если бы еще здесь, здесь, и вот здесь дополнительно ключевые параметры сбрасывать в лог, то расследование было бы в разы быстрее и проще.

26 февраля 2013 г.

Нет никакой ложки...

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

4 февраля 2013 г.

Задача с собеседования: продолжение

Поскольку в комментариях ответ нашли аж несколько раз, то сознаюсь — да, идея в том, что второй процессор это не только дополнительные 600 баксов стоимости и 70Вт энергопотребления, но еще и лишние 32Кб L1 кэша данных (а в Sandy Bridge так и лишние 256Кб L2, потому что там L2 тоже на каждое ядро). Так что, хотя в общем случае логично ожидать, что однопроцессорная версия будет быстрее (потому что не надо тратиться на синхронизацию), но если задача достаточно memory intensive (т.е. мы упираемся в скорость доступа к данным), причем фазы P1 и P2 оперируют разными данными, то в двухпроцессорном варианте данные фазы 1 будут горячими в кэше CPU1, а данные фазы 2 горячими в кэше CPU2. Получим эффективный размер L1 в 64Кб. И эффект от такого "увеличения" кэша может оказаться доминирующим, и оправдать даже расходы на синхронизацию.

31 января 2013 г.

Задача с собеседования

...Пусть у нас есть некоторая процедура обработки сообщений. Процедура состоит из двух фаз: P1 и P2. Фазы строго последовательны — P2 не может начаться, пока не закончилась P1. У нас есть датацентр, в датацентре — стойка, в стойке — сервер, в сервере — 2 процессора.

15 сентября 2012 г.

AtomicFieldUpdater optimized

AtomicXXXFieldUpdater — чудесные классы, открывающие значительную часть магии Unsafe без проблем с безопасностью и переносимостью. К сожалению, есть некоторая цена. Вот цитата из AtomicLongFieldUpdater.CASUpdater:

public void lazySet(T obj, long newValue) {
  if (obj == null || obj.getClass() != tclass || cclass != null) 
    fullCheck(obj);
           
  unsafe.putOrderedLong(obj, offset, newValue);
}
private void ensureProtectedAccess(T obj) {
  if (cclass.isInstance(obj)) 
    return;
  throw new RuntimeException (
        new IllegalAccessException("Class " + cclass.getName() + 
            " can not access a protected member of class " + tclass.getName() +
            " using an instance of " + obj.getClass().getName()
        )
  );
}
private void fullCheck(T obj) {
  if (!tclass.isInstance(obj))
    throw new ClassCastException();
  if (cclass != null)
    ensureProtectedAccess(obj);
}  

Выглядит все довольно страшно, хотя на практике в большинстве случаев все закончится на первых трех проверках: (obj == null || obj.getClass() != tclass || cclass != null). Эффект от них невелик, в моих бенчмарках замена AtomicUpdater на Unsafe давала 15-20% максимум в очень нагруженном конкурентном коде. По-видимому, дело в том, что результат этих проверок в правильно написанном коде всегда одинаков (false), поэтому предсказатель ветвлений в процессоре довольно быстро сообразит, какая из веток реализуется со 100% вероятностью, и будет спекулятивно выполнять код дальше. Тем не менее, иногда не хочется терять и этих процентов.

Хорошая новость состоит в том, что AtomicLongFieldUpdater — абстрактный класс, и никто не мешает вам написать свою реализацию. Например, взять за основу AtomicLongFieldUpdater.CASUpdater, и просто выбросить все "лишние" проверки. Результат будет практически drop-in-replacement для большинства сценариев использования.

Разумеется, у меня сразу возникла мысль сделать какую-то свою фабрику, на замену AtomicLongFieldUpdater.newUpdater(...), которая по-умолчанию делегировала бы к AtomicLongFieldUpdater.newUpdater, а при указании специального свойства -Djava.concurrent.run-faster начинала бы использовать оптимизированную версию. Плохая новость состоит в том, что так не получается: в конструкторе AtomicFieldUpdater-а проверяется, что вы можете создать AtomicUpdater только для того поля, которое вы и так можете видеть из создающего кода. Если я собираюсь обновлять private поле, то AtomicUpdater для него я смогу создать только изнутри этого же класса. И значит выбор реализации AtomicUpdater-а придется делать внутри каждого класса, его использующего.

28 июля 2012 г.

Синтаксический сахарочек

Вообще, java нас не балует синтаксическим сахаром. Лично мне это даже очень нравится — терпеть не могу выкапывать суть под горой сладкого. Из-за этого отказался от мысли перейти на Scala — побоялся диабет схватить. Но иногда хочется все-таки сделать своему компоненту такой сладенький интерфейс, чтобы пальчики оближешь. И когда я нахожу в аскетической джаве какую-нибудь карамельку — я очень радуюсь :)

Например, есть у нас такой класс-мэппер
public class Mapping{
  public String map(final String arg1, final String arg2);
}
И есть какая-то реализация, скажем SimpleImmutableMapping, и хочется сделать для его конфигурирования фабрику-билдер, типа вот такой:
public class MappingBuilder{
    public MappingBuilder map( final String arg1 ){...}
    public MappingBuilder with( final String arg2 ){...}
    public MappingBuilder to( final String mapping ){...}

    public Mapping build(){...}
}
...
final Mapping mapping = new MappingBuilder()
                           .map( "A" ).with( "B" ).to("ab")
                           .map( "C" ).with( "D" ).to("cd")
                           .map( "E" ).with( "F" ).to("ef")
                           .build();
Что мне здесь не нравится? — мне не нравится дуракоустойчивость. Особенно мне не нравится то, что ее здесь нет, и это хорошо видно на скриншоте справа (Да, это у меня такая цветовая схема, нет, глаза не устают, да, мне нравится, идите в жопу).
Что будет, если я вызову в этой точке .build()? Очевидно, ничего хорошего. В лучшем случае уже во время выполнения вылетит IllegalStateException("Can't build mapping with supplied data: first argument is not enough"). Это если я позаботился о том, как мой объект себя ведет, если его используют "неправильно". В более реальном случае будет что-нибудь вроде NullPointerException из недр метода .build(). В самом паршивом случае здесь все отработает без ошибок, а веселье начнется при использовании созданного Mapping-а где-нибудь совсем в другом месте.

Так вот, я раньше думал, что устроить в подобном Builder-е проверку времени выполнения — на яве не получится. А оказывается можно — правда так гемморойно как и все у нас, джавистов:
public class SimpleMapping {

  //код самого мэппера -- скучный и банальный
  .....

  //а вот дальше начинается треш и содомия
  //уберите от монитора женщин и детей, и глубоко вдохните 

  public interface FirstArgumentGivenState {
    public SecondArgumentGivenState with( final String arg2 );
  }

  public interface SecondArgumentGivenState {
    public FullMappingGivenState to( final String mapping );
  }

  public interface FullMappingGivenState {
    public Mapping build();
    public FirstArgumentGivenState map( final String arg1 );
  }

  private static class Builder implements
      FirstArgumentGivenState,
      SecondArgumentGivenState,
      FullMappingGivenState {

    public FirstArgumentGivenState map( final String arg1 ) {
      ...
      return this;
    }

    public SecondArgumentGivenState with( final String arg2 ) {
      ...
      return this;
    }

    public FullMappingGivenState to( final String mapping ) {
      ...
      return this;
    }

    public Mapping build() {
      ...
    }
  }

  public static FullMappingGivenState builder() {
    return new Builder();
  }
}
....
final Mapping mapping = SimpleMapping.builder()
    .map( "A" ).with( "B" ).to( "ab" )
    .map( "C" ).with( "D" ).to( "cd" )
    .map( "E" ).with( "F" ).to( "ef" )
    .build();
Попробуйте теперь вызвать что-то неправильно :)

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


По-правде, я не уверен, что придумать такое было хорошей идеей — встреть я такой адъ в чужом коде, матерился бы в голос. А ведь самому-то теперь будет сложно удержаться :)

Если серьезно, то мне кажется, делать такое в каждом Builder-е это over-engeneering. Сложность понимания "как, и зачем, черт подери, такое здесь наворочено" не окупает небольшого увеличения дуракоустойчивости. Но вот если какая-нибудь изолированная, часто используемая библиотека... Тогда к странным типам возвращаемых значений у методов Builder-а можно и привыкнуть, а вот compile time safety при широком использовании может вполне себя окупить.

Если что — похороны за ваш счет. Я предупреждал :)

UPD:Как мне подсказывает Александр в комментариях — это уже описано как паттерн Wizard. Было бы слишком оптимистично ожидать, что такую штуку еще никто не придумал. Статью рекомендую прочитать, примеры там забавные.

30 декабря 2011 г.

Thread Affinity

Peter Lawrey, которого я уже как-то упоминал, решил написать свою собственную библиотеку для привязки потоков к ядрам из джавы. Ну, понятно, с шахматами и поэтессами. Его реализация (сам код можно посмотреть здесь) изначально основывалась на JNI-обертке вокруг sched_setaffinity(3)/sched_getaffinity(3). Я не смог удержаться, и вписался -- благодаря чему теперь у него есть и "моя" реализация, использующая JNA. Буду стараться уговорить его забить на поддержку JNI -- гемморой с поддержанием portable build для сборки JNI-обертки по-моему не стоит свеч.

Что меня заинтересовало в его реализации -- так это дизайн. Вместо тривиального setAffinityMask/getAffinityMask он ввел абстракцию "блок кода, выполнение которого привязано к ядру". Выглядит это так:
public void run() {
            final AffinityLock al = AffinityLock.acquireLock();
            try {
                //performance-critical block of code
            } finally {
                al.release();
            }
        }
С текущей реализацией есть несколько проблем.

Во-первых, реализация-то есть только для unix/linux -- для платформ, поддерживающих sched_setaffinity. Моя попытка портировать на винду сходу не удалась -- SetThreadAffinity я еще нашел, а вот где взять GetThreadAffinity -- так и не разобрался. Поскольку у меня еще и нет винды для тестов -- эту часть я решил отложить.
Попытка портировать на Мак (что для меня очень актуальна) обломалась еще более серьезно -- на Маке вообще нет возможности назначать привязку. Интерфейс взаимодействия с планировщиком потоков, который представляет MacOS X начиная с 10.5+ позволяет только давать рекомендации планировщику, относительно того, что данные потоки неплохо бы поместить "как можно ближе" друг к другу -- в смысле разделяемых кэшей. Это практически обратное тому, что хочется.

Во-вторых, сама по себе идея запрещать relocation для preformance-critical (скорее, latency-critical, если уж быть точным) потоков -- она, конечно, хороша. Но это далеко не все, чего бы хотелось от интерфейса управления привязками. Навскидку, я могу придумать такие пункты:
  1. Запрещать перемещение потока во время выполнения определенного кода. Это то, что делает библиотека Питера. Т.е. мне пофигу, на каком ядре будет выполняться код, но я хочу, чтобы это ядро было фиксированным все время выполнения данного участка кода. Что я пытаюсь этим выиграть? -- я хочу не тратить время на смену контекста и прогревание кэша при перемещении потока.
  2. Закрепить ядро за конкретным потоком эксклюзивно. Расширение предыдущего пункта -- мало того, что я хочу запретить перемещение моего потока с текущего ядра, так я еще и хочу запретить перемещение любого другого потока на это ядро (и, разумеется, выпинать с этого ядра те потоки, которые уже на нем сидят сейчас). Что я хочу выиграть здесь? -- в основном, я хочу получить весь кэш ядра только для своего потока.
    Сложность здесь в том, что внутри работающей JVM есть хуева туча потоков, выполняющих всякие системные надобности. Начиная от совсем внутренних потоков JVM, типа GC/Finalizer и JIT-compiler, и кончая потоками, запускаемыми внутри стандартной библиотеки -- типа всяких таймеров, чистильщиков очередей слабых ссылок, и прочего мусора. Получить доступ к этим потокам, чтобы можно было явно запретить им использовать определенные ядра -- довольно непросто.
    Немного усиленный вариант -- запретить использование не только конкретного логического ядра, а именно физического -- т.е. в случае hyper-threading запретить использование парного аппаратного потока. Смысл такой: "а ну отъебитесь все от моего кэша".
    Дополнительная, хоть и сомнительная, опция -- распространить эту эксклюзивную привязку на всю систему. То есть не только в рамках текущего процесса JVM все потоки кроме выделенного обходят данное ядро стороной -- но и глобально во всей системе никто более на это ядро не претендует. Сомнительна эта опция потому, что кажется не очень хорошей идеей позволять конкретному приложению вмешиваться в работу планировщика потоков на уровне всей системы -- не по чину ему.
  3. Связать группу потоков (идея из MacOS X API). Т.е. я хочу, чтобы определенная группа потоков была расположена на таких ядрах, коммуникация между которыми будет максимально дешева. При этом мне все равно, какие именно это ядра.

Вопрос состоит в том, как именно максимально абстрактно соединить в одном API все эти опции...

P.S. Как мне подсказывают, это мой сотый пост за время ведения блога. Ура мне!

24 октября 2011 г.

Open Source: Retryer

У меня наконец-то дошли руки выложить что-то из своих работ в ОС. Библиотечка, созданная изначально еще во времена работы над DataGuard-ом, потом допиленная уже на нынешней работе -- Retryer.

Задача, которую она решает: часто бывает так, что какой-то код может не выполниться успешно "без причины", и если такое происходит, нужно просто попытаться выполнить его еще несколько раз -- возможно, с различными паузами между попытками. Чаще всего такое бывает с кодом, который дергает какие-то внешние сервисы -- тут может быть куча временных/случайных причин для сбоев: временная перегрузка сети, временная неработоспособность сети, временная перегрузка сервиса, перезапуск сервиса... Какую-то степень устойчивости к этим факторам предоставляют сами протоколы (например, тот же TCP какие-то сетевые сбои обрабатывает незаметно для пользователя) но этой степени часто недостаточно для целей конкретного приложения.

Вот, собственно, задачу "стучаться пока не откроют" библиотека и выполняет. Что с ней можно делать:
  1. Задать код, который нужно выполнять "пока не получится" (==он завершится без исключений)
  2. Задать стратегию задержки (back off) между отдельными попытками. Есть библиотека простых стратегий (без задержки, фиксированная пауза, линейно растущая пауза, экспоненциально растущая пауза...) + билдер/dsl для их комбинации. Например:
    Backoff
                .withExponentialGrowingDelay()
                .startingWithDelay( 1, TimeUnit.SECONDS )
                .maxTryes( 5 )
                .maxDelay( 10, TimeUnit.SECONDS )
                .build()
    
  3. Задать "фатальные ошибки" -- т.е. при некотором классе ошибок дальнейшее продолжение попыток смысла не имеет. Например, если сервис выбросил исключение ConnectionTimeout -- имеет смысл попробовать еще разок позже, авось сеть заработает. Но если сервис выкинул IncorrectProtocolVersionException, то дальше пробовать смысла нет -- мы явно ломимся куда-то не туда

Пример использования (запрос по URL-у):

private static final String URL_TO_QUERY = "http://google.com/?q=Retryer";

public static String simpleQuery( final String urlString ) throws Exception {
    final URL url = new URL( urlString );
    final InputStream is = url.openStream();
    try {
        final InputStreamReader r = new InputStreamReader( is, "ISO-8859-1" );
        try {
            return CharStreams.toString( r );
        } finally {
            r.close();
        }
    } finally {
        is.close();
    }
}

....

public static String queryRetryableComplex( final String urlQuery ) throws Exception {
    return new Retryer().doRetryable(
            new IRetryableTask<String, Exception>() {
                public String execute( final int tryNo ) throws Exception {
                    return simpleQuery( urlQuery );
                }

                public boolean isFatalReason( final int tryNo,
                                                                     final Throwable reason ) {
                    return (reason instanceof MalformedURLException);
                }
            },
            Backoff
                        .withExponentialGrowingDelay()
                        .startingWithDelay( 1, TimeUnit.SECONDS )
                        .maxTryes( 5 )
                        .maxDelay( 10, TimeUnit.SECONDS )
                        .build()
    );
}

здесь мы будем пытаться запросить гугл с экспоненциально растущей задержкой, начиная с 1 секунды, но не более 10 секунд, и не более 5 раз подряд. При этом мы не будем повторять запрос если он выбросит MalformedURLException (какой смысл-то?).

С удовольствием послушаю всяческую ругань. Обещаю активно и интересно ругаться в ответ :)