Re[5]: А вы используете массивы?
От: c-smile Канада http://terrainformatica.com
Дата: 11.01.09 05:24
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, c-smile, Вы писали:


CS>>Вставка в начало/середину массива гораздо лучше оптимизируется современными процессорами.

S>А можно мне как-то пояснить, что за оптимизации имеются в виду?

memcpy на основе

rep
movsl


вельми как эффективна.

В зависимости от задачи — типа элемента последовательности, набора базовых операций и пр.
array based списки оказываются эффективнее чем списки.

Но опять же смотря для чего. Есть ситуации когда список эффективнее.
Я просто хочу сказать следующее: при вставке в середину списка далеко не всегда list эффективнее чем array.

CS>>Для эффективной вставки в середину список кстати должен быть двунаправленным.

S>Не обязательно.

Слушай, и ты и я знаем как эффективно реализовать вставку в однонаправленный список элементов.
Это первй курс или чего-то там. Также мы с тобой знаем что для общего случая универсального решения нет.
Нужно сканировать весь список для вставки элемента перед данным.

CS>>И даже в этом случае массивы могут оказаться лучшим выбором ибо у них наименьшие накладные расходы из всех коллекций — больше информации влезет в "доступный объем адресного пространства".

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

Колллекции у которых размер соизмерим с размером памяти это вообще отдельная тема —
там своеобразные струтуры данных.
Т.е. это к спискам/массивам имеет весьма отдаленное отношение. Там список где элементы имеют
адрес следующего элемента физически не применим как абстракция. Поэтому о чем речь-то собственно?
Re[6]: А вы используете массивы?
От: thesz Россия http://thesz.livejournal.com
Дата: 11.01.09 09:22
Оценка:
CS>>>Вставка в начало/середину массива гораздо лучше оптимизируется современными процессорами.
S>>А можно мне как-то пояснить, что за оптимизации имеются в виду?
CS>memcpy на основе
CS>
CS>rep
CS>movsl
CS>

CS>вельми как эффективна.

Ты бы посмотрел на memcpy внутри.

Это раз.

Пункт два — это только один тип процессора. Что будет на ARM? На MIPS? На SPARC?

CS>В зависимости от задачи — типа элемента последовательности, набора базовых операций и пр.

CS>array based списки оказываются эффективнее чем списки.

Могут оказаться, а не оказываются.

Это пункт три.

CS>Но опять же смотря для чего. Есть ситуации когда список эффективнее.

CS>Я просто хочу сказать следующее: при вставке в середину списка далеко не всегда list эффективнее чем array.

Если нам надо последовательно перебирать и вставлять в обнаруженное место (merge в mergesort, например) и это происходит более, чем один раз (merge в mergesort, например), то массив не подойдёт.

CS>>>Для эффективной вставки в середину список кстати должен быть двунаправленным.

S>>Не обязательно.
CS>Слушай, и ты и я знаем как эффективно реализовать вставку в однонаправленный список элементов.
CS>Это первй курс или чего-то там. Также мы с тобой знаем что для общего случая универсального решения нет.
CS>Нужно сканировать весь список для вставки элемента перед данным.

Надо строить алгоритмы индуктивно, это проще в конечном счёте. См. merge в mergesort, например.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[6]: А вы используете массивы?
От: Sinclair Россия https://github.com/evilguest/
Дата: 11.01.09 09:53
Оценка:
Здравствуйте, c-smile, Вы писали:


CS>вельми как эффективна.

Так, для справки: rep movsl — это один из самых хреновых способов копирования на современных процессорах. Никогда не задумывался, почему компиляторы редко используют префикс rep? Вот как раз потому, что он хреново оптимизируется процессорами.

CS>Но опять же смотря для чего. Есть ситуации когда список эффективнее.

CS>Я просто хочу сказать следующее: при вставке в середину списка далеко не всегда list эффективнее чем array.
Случаи, когда array сопоставим со списком при вставке в середину, исчерпываются очень маленьким размером этого array.
Как только вылетел за пределы кэша — всё, считай приехали

CS>Нужно сканировать весь список для вставки элемента перед данным.

А не надо вставлять "перед данным". Надо вставлять "после данного". И всё станет хорошо

CS>Т.е. это к спискам/массивам имеет весьма отдаленное отношение. Там список где элементы имеют

CS>адрес следующего элемента физически не применим как абстракция. Поэтому о чем речь-то собственно?
О том, что не нужно считать "список, где элементы имеют адрес следующего элемента" единственной альтернативой массиву.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: А вы используете массивы?
От: elmal  
Дата: 11.01.09 10:02
Оценка: -1
Здравствуйте, Mamut, Вы писали:

M>А как часто вы используете массивы?

Массивы используют все, так или иначе. Массив это фича именно языка, и множество высокоуровневых коллекции внутри сделаны через массивы. Множество низкоуровневых вещей (например таблица виртуальных функций) — тоже представляют собой массив. Очень хорошая вещь на низком уровне, раз память по существу массив, то соответствующая структура должна быть и в языке. Вот только мое ИМХО, что массивы в чистом виде вряд ли стоит использовать, лучше уж написать враппер, если не хватает стандартных библиотечных структур данных. А относительно массивов в чистом виде — я их перестал использовать 5 лет назад, если и приходится использовать, то для взаимодействия с велосипедами, которые написаны черти как давно (синтаксис массивов не помню, каждый раз в справочник лезу ).
Кстати относительно скорости. Тут на форуме много программистов старой школы возмущаются, что новое поколение забыло про возможность доступа по произвольному индексу, всегда пользуются итераторами и т.д. А по существу то: оперативная память уже давно стала не с произвольным доступом, а с последовательным, соответственно прыгать с одного индекса массива на произвольный другой довольно накладно становится. И в небиблиотечным коде лучше пользоваться итераторами, а не бегать прямо по индексу. То, что было хорошо раньше, на современном железе уже далеко не столь хорошо, многие старые приемы просто не работают, они ухудшают скорость а не улучшают. Я уж молчу про читаемость. Индекс массива это по существу числовой адрес в памяти. Скрывать бы эти адреса не мешало.
Re[2]: А вы используете массивы?
От: Sinclair Россия https://github.com/evilguest/
Дата: 11.01.09 11:32
Оценка:
Здравствуйте, elmal, Вы писали:
M>>А как часто вы используете массивы?
E>Массивы используют все, так или иначе. Массив это фича именно языка, и множество высокоуровневых коллекции внутри сделаны через массивы. Множество низкоуровневых вещей (например таблица виртуальных функций) — тоже представляют собой массив. Очень хорошая вещь на низком уровне, раз память по существу массив, то соответствующая структура должна быть и в языке.
Угу. Вот только память нифига не ведет себя как массив. Потому как основная характеристика контракта массива — это O(1) сложность для операции array[int i].
Это так, к слову.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: А вы используете массивы?
От: elmal  
Дата: 11.01.09 11:45
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Угу. Вот только память нифига не ведет себя как массив. Потому как основная характеристика контракта массива — это O(1) сложность для операции array[int i].

Можно поподробнее, а то что-то не понял мысль? А какая же тогда сложность будет для чтения из нужной ячейки памяти? Таже самая вроде. Даже если учитывать многоуровневое кеширование, в среднем один черт будет O(1).
Re[4]: А вы используете массивы?
От: Sinclair Россия https://github.com/evilguest/
Дата: 11.01.09 12:07
Оценка:
Здравствуйте, elmal, Вы писали:

E>Можно поподробнее, а то что-то не понял мысль?

Нужно учитывать кэш.
E>А какая же тогда сложность будет для чтения из нужной ячейки памяти? Таже самая вроде. Даже если учитывать многоуровневое кеширование, в среднем один черт будет O(1).
Во-первых, невредно помнить, что адреса, которыми мы манипулируем — виртуальные. И маппинг в физические может привести, в том числе, и к подкачке.
Во-вторых, таки да — кэш вносит свою лепту.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: А вы используете массивы?
От: elmal  
Дата: 11.01.09 12:56
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Во-первых, невредно помнить, что адреса, которыми мы манипулируем — виртуальные. И маппинг в физические может привести, в том числе, и к подкачке.

S>Во-вторых, таки да — кэш вносит свою лепту.
Так с массивом (достаточно большим) тоже самое вроде. Массив то находится в памяти, и все особенности памяти применительны и к массиву. И ни черта в общем случае будет не O(1). O(1) то будет тоже не для любого массива, а для сферического массива в вакууме (либо для массива небольшого размера). Хотя ... даже размер не важен, когда мы захотим обратиться к элементу массива, не факт что массив будет загружен в оперативную память, в результате чтение элемента может оказаться очень долгим.
Re[7]: А вы используете массивы?
От: minorlogic Украина  
Дата: 11.01.09 16:09
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, c-smile, Вы писали:



CS>>вельми как эффективна.

S>Так, для справки: rep movsl — это один из самых хреновых способов копирования на современных процессорах. Никогда не задумывался, почему компиляторы редко используют префикс rep? Вот как раз потому, что он хреново оптимизируется процессорами.

Не совсем , кажется в новых процах это пофиксили. Не уверен .
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[2]: А вы используете массивы?
От: Gaperton http://gaperton.livejournal.com
Дата: 11.01.09 17:38
Оценка: +1 -1
Здравствуйте, AndrewVK, Вы писали:

M>>А как часто вы используете массивы?


AVK>Часто. К примеру, прекрасное средство оборвать ленивость итераторов. Неплохо массивы смотрятся в качестве элементов контракта в виду своей легковесности и стандартности, а если нужно переменное число параметров, то вообще альтернативы нет.


Гхм, дайте мне тож подколоть штоль.

template < class It >
void variable_arg_num_func( It i_argListBegin, It i_argListEnd )


И где у нас разница между массивом и списком? Что хошь, то и передавай. То же касается ленивости итераторов и прочего перечисленного. Эт конечно дремучий С++, но разве в новомодных С# нельзя делать так же?
Re[5]: А вы используете массивы?
От: Don Reba Канада https://stackoverflow.com/users/49329/don-reba
Дата: 11.01.09 18:31
Оценка:
Здравствуйте, Sinclair, Вы писали:

E>>А какая же тогда сложность будет для чтения из нужной ячейки памяти? Таже самая вроде. Даже если учитывать многоуровневое кеширование, в среднем один черт будет O(1).

S>Во-первых, невредно помнить, что адреса, которыми мы манипулируем — виртуальные. И маппинг в физические может привести, в том числе, и к подкачке.
S>Во-вторых, таки да — кэш вносит свою лепту.

Но на сложность то это не влияет. В любом случае, доступ к ячейке номер 1 не отличается от доступа к ячейке номер 100.
Ce n'est que pour vous dire ce que je vous dis.
Re[6]: А вы используете массивы?
От: Sinclair Россия https://github.com/evilguest/
Дата: 12.01.09 04:16
Оценка:
Здравствуйте, Don Reba, Вы писали:

DR>Но на сложность то это не влияет. В любом случае, доступ к ячейке номер 1 не отличается от доступа к ячейке номер 100.

Я бы не сказал. Доступ к ячейке i+1 получается быстрее, чем к i+100. В итоге, итерирование массива оказывается дешевле, чем random access
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[7]: А вы используете массивы?
От: Don Reba Канада https://stackoverflow.com/users/49329/don-reba
Дата: 12.01.09 04:57
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Я бы не сказал. Доступ к ячейке i+1 получается быстрее, чем к i+100. В итоге, итерирование массива оказывается дешевле, чем random access


О(1) не означает, что время доступа ко всем элементам одинаковое. Сложность доступа к виртуальной памяти O(1), ограниченная сверху длительностью page fault. С контрактом массива всё в порядке.
Ce n'est que pour vous dire ce que je vous dis.
Re[8]: А вы используете массивы?
От: Sinclair Россия https://github.com/evilguest/
Дата: 12.01.09 05:58
Оценка:
Здравствуйте, Don Reba, Вы писали:
DR>О(1) не означает, что время доступа ко всем элементам одинаковое. Сложность доступа к виртуальной памяти O(1), ограниченная сверху длительностью page fault. С контрактом массива всё в порядке.
Ок, убедили.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[9]: Интерфейс и контракт
От: Qbit86 Кипр
Дата: 18.03.09 12:44
Оценка:
Здравствуйте, gandjustas, Вы писали:

G>Вообще с чего это в контракт входят временные асимптотики? временные асимптотики — деталь реализации.


Krzysztof Cwalina «Framework Design Guidelines», 2nd rdition:

I often hear people saying that interfaces specify contracts. I believe this is a dangerous myth. Interfaces, by themselves, do not specify much beyond the syntax required to use an object. The interface-as-contract myth causes people to do the wrong thing when trying to separate contracts from implementation, which is a good engineering practice. Interfaces separate syntax from implementation, which is not that useful, and the myth provides a false sense of doing the right engineering.

In reality, the contract is semantics, and these can actually be nicely expressed with some implementation.

Глаза у меня добрые, но рубашка — смирительная!
Re: А вы используете массивы?
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 18.03.09 15:38
Оценка:
Здравствуйте, Mamut, Вы писали:

M>via http://damienkatz.net/2008/12/arrays_whats_the_point_good_qu.html


M>[q]

M>В чем фишка массивов? Хороший вопрос

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

Получается у меня лично:
1) Массивы-константы. Частный случай при метапрограммировании, когда по упрощенному файлу описания одна программа генерит в виде исходника массив данных для другой программы.
2) Когда на этапе компиляции известна длина массива или это конфигурационный параметр. Буфер при системном вызове.
3) При чтении бинарных файлов, когда массивы напрямую содержаться в спецификации. Также при доступе к памяти по указателю
Re[3]: А вы используете массивы?
От: vdimas Россия  
Дата: 21.03.09 05:50
Оценка: 2 (1) +1
Здравствуйте, _FRED_, Вы писали:

_FR>Какие преимущества (иными словами, "чем лучше") будет иметь тип возвращаемого значения T[] перед IList<T> и в каких ситуациях?


Как-то делал ручную бинарную сериализацию, т.к. встроенная слишком долго работала, да еещ и очень говорливаяя была. Так вот, при дальнейшем повышении эффективности, только замена IList<T> на T[] в структуре данных где можно, позволила выиграть в скорости сериализации почти в 5 раз (!!!).

Признаюсь, много думал.
Хотя, ничего удивительного, если посмотреть на генерируемый код. В случае IList<T>, даже если реально подать массив, то енумератор для foreach будет создан как динамический объект, и у этого енумератора ну жутко неэффективный код (см. ArrayEnumerator в рефлекторе). Если же компилятор знает, что foreach делается по массиву, то никаких динамических объектов не создаётся, а сам код енумератора легковесен и прост. Точно так же имеются большие накладные расходы для доступа по индексу в случае IList<> и гораздо меньшие для массивов в циклах for.

А итог написания ручной бинарной сериализации был таков: на файлах в районе 10MB уменьшение примерно втрое размера и увеличение скорости сохранения и считывания примерно в 50 раз.
Re[5]: А вы используете массивы?
От: vdimas Россия  
Дата: 21.03.09 06:21
Оценка:
Здравствуйте, _FRED_, Вы писали:

_FR>Так вот прям List<>? Не IList<>?


Вообще, ICollection<>, IList<> — весьма "жирные" интерфейсы, и неудобны, если предполагается куча своих миниатюрных read-only коллекций.

Так что, IEnumerable<> руль, а для других случаев для себя я ввожу:


interface ICountable<T> : IEnumerable<T> {
  int Count { get; }
}

interface IIndexable<T> : ICountable<T> {
  T this[int i] { get; }
}



Заодно имею решение по иммутабельности массивов без лишней коссвенности, которая чудесно оптимизируется как для foreach, так и для for циклов:
struct ArrayBox<T> : IIndexable<T>
{
    private T[] array;

    public ArrayBox(T[] a)
    {
        if (a == null) throw new ArgumentNullException("a");
        array = a;
    }

    public T this[int i] { get { return array[i]; } }
    public int Count { get { return array.Length; } }

    public static implicit operator ArrayBox<T>(T[] array)
    {
        return new ArrayBox<T>(array);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new Enumerator(array);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    struct Enumerator : IEnumerator<T>
    {
        T[] array;
        int i;

        internal Enumerator(T[] a)
        {
            array = a;
            i = -1;
        }

        public T Current
        {
            get { return array[i]; }
        }

        public void Dispose()
        {
        }

        object System.Collections.IEnumerator.Current
        {
            get { return array[i]; }
        }

        public bool MoveNext()
        {
            int tmp = i + 1;
            if (tmp < array.Length)
            {
                i = tmp;
                return true;
            }

            return false;
        }

        public void Reset()
        {
            i = -1;
        }
    }
}
Re[3]: А вы используете массивы?
От: vdimas Россия  
Дата: 21.03.09 06:27
Оценка:
Здравствуйте, Gaperton, Вы писали:


G>
G>template < class It >
G>void variable_arg_num_func( It i_argListBegin, It i_argListEnd )
G>


G>И где у нас разница между массивом и списком? Что хошь, то и передавай. То же касается ленивости итераторов и прочего перечисленного. Эт конечно дремучий С++, но разве в новомодных С# нельзя делать так же?


Не только можно, но и нужно:
void variable_arg_num_func<T>(IEnumerable<T> args) { ... }
void variable_arg_num_func<T>(params T[] args) { variable_arg_num_func((IEnumerable<T>)args); }


Второй случай — синтаксический хелпер, чтобы аргументы прямо при вызове записывать.
Re[7]: А вы используете массивы?
От: vdimas Россия  
Дата: 21.03.09 06:37
Оценка:
Здравствуйте, thesz, Вы писали:

T>Ты бы посмотрел на memcpy внутри.


T>Это раз.


Ты бы посмотрел на генерируемый код с влюченной оптимизацией, это раз. Никакого вызова ф-ии memcpy нет, прямо по месту указанные инструкции инжектятся.

T>Пункт два — это только один тип процессора. Что будет на ARM? На MIPS? На SPARC?


Если углубляться далее, то у многих микроконтроллеров кол-во индексных регистров очень ограничено, так что массивы там рулят всё-равно.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.