Здравствуйте, vdimas, Вы писали:

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

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

Почему?

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

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

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

Чем это будет лучше стандартных интерфейсов? Хуже будет тем, что не поддерживается BCL. Первый вариант — это ICollection<> { ReadOnly = true }, второй ничем функционально не отличается от readonly-списка. ИМХО, как раз тот случай когда без необходимости вводятся и размножаются сущности, которые дублируют то, что и так уже есть в стандартной библиотеке. А выхлоп-то какой? То, что при нажатии точки в студии список intellisence вылезает покороче? Фи, зато экземпляр readonly-коллекции, например, я могу передать в Enumerable.ToArray() и получу более эффективный результат чем с использованием доморощенного ICountable<> и подобных примеров можно найти множество.

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

Тем, кого раздражает "жирность" интерфейсов надо принять, что в дизайне BCL широко используется Optional Features Pattern. Его можно сколь угодно много и часто называть неудачным решением (попробуйте сами сначала спроектировать библиотеку с десятками тысяч типов, которую будут использовать сотни тысяч пользователей совершенно разной подготовки) и предлагать свои, "лучшие", но _невозможно_ отрицать то, что стандартная библиотека построена с частым применением этого паттерна. Это касается и коллекций, и Stream-ов и, наверное, многих других кусков.

Так я всё же хочу знать чем предложеное решение с ICountable\IIndexable лкучше стандартных, если не забывать того, что если интерфейс объявлен public то виден снаружи и потребуется кому-то, кому придётся крестить его со стандартной библиотекой.

V>Заодно имею решение по иммутабельности массивов

Во. Это очень серьёзный вопрос: иммутабельность массивов. Для чего? В куске кода, который предназначен для быстрых вычислений и которым должен работать так быстро, как это только возможно, ИМХО, фиолетово, иммутабельный там в нём массив или нет: у него другая задача. Да и не получился он неизменяемым: одна видимость, то есть интерфейс.

Для использования в public API я бы предпочёл ReadOnlyCollection<>.

V>без лишней коссвенности, которая чудесно оптимизируется как для foreach, так и для for циклов:

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

V>    struct Enumerator : IEnumerator<T>

"Косвенность" таки наблюдается в том, что происходит боксинг Enumerator-а. Зачем было оптимиздить© до структуры

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

Польщён оказываемым вниманием.

Возвращаясь к теме могу сказать, что movsd (привык!) далеко не самый оптимальный метод переноса данных.

T>>Пункт два — это только один тип процессора. Что будет на ARM? На MIPS? На SPARC?
V>Если углубляться далее, то у многих микроконтроллеров кол-во индексных регистров очень ограничено, так что массивы там рулят всё-равно.

MOVSD на ARM/MIPS/SPARC нет. Ты ушёл в сторону от темы.

И всё равно, я не понимаю, почему ограничение на количество индексных регистров приводит к рулению массивов.

Здравствуйте, _FRED_, Вы писали:

_FR>Чем это будет лучше стандартных интерфейсов? Хуже будет тем, что не поддерживается BCL. Первый вариант — это ICollection<> { ReadOnly = true }, второй ничем функционально не отличается от readonly-списка. ИМХО, как раз тот случай когда без необходимости вводятся и размножаются сущности, которые дублируют то, что и так уже есть в стандартной библиотеке. А выхлоп-то какой?

Там гораздо больше методов надо реализовать, которые реально не используются в сценариях. Опять же, всё это исключительно в private/internal контрактах, так что "выхлоп" я регулирую самостоятельно. Если дальнейшие операциюю потребуют IList<> или ICollection, то соотвествующий контракт будет на них.

_FR>зато экземпляр readonly-коллекции, например, я могу передать в Enumerable.ToArray() и получу более эффективный результат чем с использованием доморощенного ICountable<> и подобных примеров можно найти множество.


Кстати, именно ToArray() реализацию для своих контрактов я сделал, ибо других подобных примеров в моём случае как раз нифига не множество. Опять же, я не настаиваю. Я даже считаю обсуждение самого факта "стоит или не стоит" неуместным, плюсы и минусы слишком очевидны, просто показал, что для некоторых ситуаций (большого кол-ва внутренних read-only членов API) более чем удобно.


_FR>Нет, никто не мешает взять и написать свою замену BCL и даже FCL, только надо понимать для чего это делается, какие плюсы и, главное, минусы проявятся.

Да не надо усложнять — там всё очевидно.
1. более простая реализация коллекций.
2. возможность использовать легковесные обёртки для read-only коллекций. На самом деле, это было ключевое требование — уменьшение коссвенности, и оно потянуло №1 как ср-во не поломать себе пальцы, реализуя стандартные, но никогда неиспользуемые методы в своих типах. У меня там много еще своего, например, легковесный struct EmbeddedList<>, который используется как замена List<> в приватных полях и локальных переменных, и даёт нехилый прирост быстродействия в сценариях доступа по индексу.


_FR>Тем, кого раздражает "жирность" интерфейсов надо принять, что в дизайне BCL широко используется Optional Features Pattern. Его можно сколь угодно много и часто называть неудачным решением (попробуйте сами сначала спроектировать библиотеку с десятками тысяч типов, которую будут использовать сотни тысяч пользователей совершенно разной подготовки) и предлагать свои, "лучшие", но _невозможно_ отрицать то, что стандартная библиотека построена с частым применением этого паттерна. Это касается и коллекций, и Stream-ов и, наверное, многих других кусков.

Да понятно всё, но в приватных или промежуточных вычислениях мы имеем право выбирать наиболее удобный для себя путь. Тем более, что у меня такая тема, где оно того стоит.

_FR>Так я всё же хочу знать чем предложеное решение с ICountable\IIndexable лкучше стандартных, если не забывать того, что если интерфейс объявлен public то виден снаружи и потребуется кому-то, кому придётся крестить его со стандартной библиотекой.

Не виден снаружи. Очень редко виден как protected, когда заранее известно назначение и сценарии использования.

V>>Заодно имею решение по иммутабельности массивов

_FR>Во. Это очень серьёзный вопрос: иммутабельность массивов. Для чего? В куске кода, который предназначен для быстрых вычислений и которым должен работать так быстро, как это только возможно, ИМХО, фиолетово, иммутабельный там в нём массив или нет: у него другая задача. Да и не получился он неизменяемым: одна видимость, то есть интерфейс.

Как это не получился неизменяемым? Доступ к внутреннему array возможен только через рефлексию.

_FR>Для использования в public API я бы предпочёл ReadOnlyCollection<>.

Так и делается, исключительно для public API создаётся закешированная переменная.

V>>без лишней коссвенности, которая чудесно оптимизируется как для foreach, так и для for циклов:
_FR>

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

V>>    struct Enumerator : IEnumerator<T>
_FR>

_FR>"Косвенность" таки наблюдается в том, что происходит боксинг Enumerator-а. Зачем было оптимиздить© до структуры

Это я тут описался, в реальном коде публичный GetEnumerator() возвращает тип Enumerator, разумеется.

Здравствуйте, vdimas, Вы писали:

V>>>Заодно имею решение по иммутабельности массивов
_FR>>Во. Это очень серьёзный вопрос: иммутабельность массивов. Для чего? В куске кода, который предназначен для быстрых вычислений и которым должен работать так быстро, как это только возможно, ИМХО, фиолетово, иммутабельный там в нём массив или нет: у него другая задача. Да и не получился он неизменяемым: одна видимость, то есть интерфейс.
V>Как это не получился неизменяемым? Доступ к внутреннему array возможен только через рефлексию.

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

V>>>без лишней коссвенности, которая чудесно оптимизируется как для foreach, так и для for циклов:

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

V>>>    struct Enumerator : IEnumerator<T>

_FR>>"Косвенность" таки наблюдается в том, что происходит боксинг Enumerator-а. Зачем было оптимиздить© до структуры

V>Это я тут описался, в реальном коде публичный GetEnumerator() возвращает тип Enumerator, разумеется.

Я так и подозревал Как-то nikov очень прикольные грабли подобной оптимизации показывал, (потом постараюсь отыскать, сейчас выходной всё-таки).

Здравствуйте, thesz, Вы писали:

T>Польщён оказываемым вниманием.

Случайно, не всегда смотрю на автора перед ответом.


T>Возвращаясь к теме могу сказать, что movsd (привык!) далеко не самый оптимальный метод переноса данных.

Если есть полезная информация, то поделись, а не намекай загадочно.


T>MOVSD на ARM/MIPS/SPARC нет. Ты ушёл в сторону от темы.

Если речь зашла о других архитектурах, то почему я ушёл от темы?


T>И всё равно, я не понимаю, почему ограничение на количество индексных регистров приводит к рулению массивов.

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

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

T>>Возвращаясь к теме могу сказать, что movsd (привык!) далеко не самый оптимальный метод переноса данных.
V>Если есть полезная информация, то поделись, а не намекай загадочно.

Целочисленные команды SSE, например. 128 бит (16 байт) за раз. Разворачивание цикла ещё прибавляет скорости.

Я, как-то, даже FPU x86 приспособил для переноса.

К сожалению, давно было.

T>>MOVSD на ARM/MIPS/SPARC нет. Ты ушёл в сторону от темы.
V>Если речь зашла о других архитектурах, то почему я ушёл от темы?

Обсуждение шло про перенос. Более того, про вставку в середину массива с использованием movsd

Автор: thesz
Дата: 11.01.09

.

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

T>>И всё равно, я не понимаю, почему ограничение на количество индексных регистров приводит к рулению массивов.
V>Потому что перебрать сплошной массив памяти можно с помощью одного индексного регистра, которые к тому же почти всегда имеют команду приращения без задействования аккумулятора. Для перебора же связанного списка нам надо или 2 индексных регистра (а их иногда всего 2), или использовать промежуточные регистры, чтобы взять запомнить адрес следующего узла списка и затем этот адрес загрузить опять в индексный регистр, в итоге код, обслуживающий собственно перебор списка, может оказаться тяжелее целевых полезных операций.

Будь добр, покажи, как это так "надо или 2 индексных регистра (а их иногда всего 2), или использовать промежуточные регистры, чтобы взять запомнить адрес следующего узла списка и затем этот адрес загрузить опять в индексный регистр". Мне, как всегда, непонятно.

Я вижу здесь всего один регистр и адресацию со смещением.

V>А вообще, подобные темы вряд ли достойны обсуждения, ибо универсальное правило тут одно — это следование требованиям. Если есть требования эффективности, то надо добиваться эффективности для конкретной платформы. Если эта эффективность будет заключаться в отказе от сплошных массивов (полно и таких сценариев), я тоже с удовольствием от них отказываюсь, не затрудняя себя сомнениями выбора. А если конкретное место не критично, то всегда правильней выбирать наиболее выразительный в исходном коде вариант. Собственно, всё.

Не могу не согласиться.

Здравствуйте, thesz, Вы писали:

T>Будь добр, покажи, как это так "надо или 2 индексных регистра (а их иногда всего 2), или использовать промежуточные регистры, чтобы взять запомнить адрес следующего узла списка и затем этот адрес загрузить опять в индексный регистр". Мне, как всегда, непонятно.
T>Я вижу здесь всего один регистр и адресацию со смещением.

В различных микроконтроллерах (навскидку — PIC, x48-x51, AVR) загрузить данные в один из рабочих регистров в файле, или выполнить арифм. операцию с ячейкой памяти (прибавить к аккумулятору, например) можно только через индексный регистр, в него предварительно заносится адрес ячейки, которую надо прочесть. Никакой адресации со смещением нет, есть косвенная адресация через номер индексного регистра. Сама система команд у некоторых кристаллов заточена под эти операции, т.к. есть команды чтения/записи через индексный регистр с пре-/пост- инкрементом/декрементом.

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

Т.е. на такую строку:

a = *ptr++;

нужна всего одна инструкция процессора.

А здесь 3 инструкции:

a = ptr->data;  // a = *ptr++
ptr = ptr->next; // tmp = *ptr; ptr = tmp;

Здравствуйте, _FRED_, Вы писали:


_FR>Очень просто: структура хранит ссылку на переданный ей массив, соответственно тот, кто передал массив так же обладает этой ссылкой и может изменять внутреннее состояние массива и структуры. Состояние массива нельзя изменить через интерфейс структуры, но можно по-другому, без reflection, законными путями. Неизменяемый тип является неизменяемым только тогда, когда все поля этого типа так же являются неизменяемыми.

Да, такой сценарий возможен, но он аналогичен преднамеренному делению на 0 в расчётах. Чтобы не наступить на эту граблю, не надо всё время оборачивать этой обёрткой некий массив, достаточно в самом классе хранить уже обёрнутый массив. И метод, который его формирует, тоже должен возвращать не исходный массив, а этот иммутабельный тип, и тогда всё будет ok.



V>>Это я тут описался, в реальном коде публичный GetEnumerator() возвращает тип Enumerator, разумеется.

_FR>Я так и подозревал Как-то nikov очень прикольные грабли подобной оптимизации показывал, (потом постараюсь отыскать, сейчас выходной всё-таки).

Интересно будет посмотреть, ибо у меня своих value-type енумераторов, скажем прямо, прилично.

Здравствуйте, vdimas, Вы писали:

V>>>Это я тут описался, в реальном коде публичный GetEnumerator() возвращает тип Enumerator, разумеется.
_FR>>Я так и подозревал Как-то nikov очень прикольные грабли подобной оптимизации показывал, (потом постараюсь отыскать, сейчас выходной всё-таки).
V>Интересно будет посмотреть, ибо у меня своих value-type енумераторов, скажем прямо, прилично.

[Этюд] GetEnumerator

Автор: nikov
Дата: 27.08.08

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

Довольно часто. В большинстве языков программирования массивы — самый простой способ создания lookup table. А таблички позволяют эффективно отделить мух от котлет и используются часто

Здравствуйте, _FRED_, Вы писали:


_FR>[Этюд] GetEnumerator

Автор: nikov
Дата: 27.08.08

Тю блин, енумератор там никаким боком, это скорее к автосвойстам автотипов. Если бы в автотипе генерировалось поле, а не св-во, никакого косяка не было бы.

Здравствуйте, Mamut, Вы писали:

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

Disclaimer:
1) Приведённые ниже рекомендации не обязательно отражают точку зрения Qbit'а.
2) Ввиду плохого качества pdf-версии книжки я не использовал copy'n'paste, а набирал вручную. Так что возможны опечатки.
3) Прежде чем спрашивать здесь «а почему так, а не иначе?» рекомендуется заглянуть в первоисточник. Я просто отобрал резюме, перепечатывать обоснования желания нет.

245:
DO prefer using collections over arrays in public APIs.

251:
DO NOT use ArrayList or List<T> in public APIs.

// bad design
public class Order {
  public List<OrderItem> Items { get { ... } }
}
// good design
public class Order {
  public Collection<OrderItem> Items { get { ... } }
}

252:
DO use the least-specialized type possible as a parameter type. Most members taking collections as parameters use the IEnumerable<T> interface.

AVOID using ICollection<T> as a parameter just to access the Count property.
Instead, consider using IEnumerable<T> and dynamically checking whether the object implements ICollection<T>.

public List<T>(IEnumerable<T> collection) {
  // check if it implements ICollection
  ICollection<T> col = collection as ICollection<T>;
  if (col != null)
    this.Capasity = col.Count;
  foreach (T item in collection)
    Add(item);
}

253:
DO NOT provide settable collection properties.
Users can replace the contents of the collection by clearing the collection first and then adding the new contents.

// bad design
public class Order {
  public Collection<OrderItem> Items { get { ... } set { ... } }
  ...
}
// good design
public class Order {
  public Collection<OrderItem> Items { get { ... } }
  ...
}

256:
DO NOT return null values from collection properties or from methods returning collections. Return an empty collection or an empty array instead.
Users of collection properties often assumes that the following code will always work:

IEnumerable<string> list = GetList();
foreach (string name in list) {
  ...
}

The general rule is that null and empty (0 item) collections or arrays should be treated the same.

257:
DO NOT return snapshot collections from properties. Properties should return live collections.
Property getters should be very lightweight operations. Returning a snapshot requires creating a copy of an internal collection in an O(n) operation.

public class Directory {
  public Directory(string root);
  public IEnumerable<FileInfo> Files { get; } // live
  // or
  public FileInfoCollection GetFiles(); // snapshot
}

258:
DO prefer collections over arrays.

CONSIDER using arrays in a low-lewel APIs to minimize memory consumption and maximise performance.

DO use byte arrays instead of collections of bytes.

259:
DO NOT use arrays for properties if the property would have to return a new array (e.g., a copy of internal array) every time the property getter is called. This ensures that users will not write the following inefficient code:

// bad design
for (int index = 0; index < customer.Orders.Length; index++)
  Console.WriteLine(customer.Orders[i]);

Источник:

Мне кажется это меньше имеет отношения к массивам , а больше к специфике использования определенных языков и библиотек. (попробую угадать , это C#).

Здравствуйте, elmal, Вы писали:

E>Индекс массива это по существу числовой адрес в памяти. Скрывать бы эти адреса не мешало.
Как раз индекс массива — это число элементов относительно его начала. Потому к адресам оно ну никак не относится — сам массив можно двигать и перераспределять. В отличие от связанных списков, элементы которых так и остаются "прибитыми" к конкретным адресам (дефрагментацию GC в расчет не берем — это внешнее вмешательство).

И еще плюс массивов — работа с ним идет как с единицей распределения памяти, а не кучей маленьких объектов в хипе.

Здравствуйте, Mamut, Вы писали:

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

постоянно

You will always get what you always got
  If you always do  what you always did