доступ по указателю

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

доступ по указателю

Anton Maksimenkov-2
Доброго времени.

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

Есть некая идейка, для простоты представим пару вариантов:

Вариант 1. Структура, большая, содержит всё что надо
struct big {
int uid;
x  va;
x  vb;
x  v1;
x  v2;
...
x v10;
}

Вариант 2. Структура, маленькая, содержит минимум инфы и указатель на
"подструктуру", большую, где залегает основная инфа.
struct idx {
int uid;
x  va;
x  vb;
struct med *pb;
}
struct med {
x  v1;
x  v2;
...
x v10;
}

Было бы интересно услышать мнения насколько медленнее будет вариант2,
т.е. через idx->pb->v..., по сравнению с вариантом1, где доступ сразу
через big->v... ?

--
antonvm
Reply | Threaded
Open this post in threaded view
|

Re: доступ по указателю

Илья А. Коваленко

Вы меня извините, а в чем вопрос, собссно ? :) то что двойное обращение через указатель выполняется в два раза дольше - самоочевидно.

и на самом деле у вас больший выбор:

1. включить члены подструктуры (ваш  1)
2. включить экземпляр подструктуры
3. включить поинтер (или ссылку) на подструктуру (ваш  2)
4. наследовать от подструктуры (C++, разновидность п. 2)
5+ то же самое но поменять структуру и подструктуру
10. наконец использовать две структуры параллельно (например, связав их через третью структуру)

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

С уважением.

Reply | Threaded
Open this post in threaded view
|

Re: доступ по указателю

Anton Maksimenkov-2
1 декабря 2010 г. 16:30 пользователь Илья А. Коваленко
<[hidden email]> написал:
> Вы меня извините, а в чем вопрос, собссно ? :) то что двойное обращение через указатель выполняется в два раза дольше - самоочевидно.

мда, видимо я слишком уж лаконично выразился. извиняюсь.

Более конкретный вопрос такой: если происходит несколько обращений,
либо к одной и той же idx->pb->v1, либо к некоторым idx->pb->v1,
idx->pb->v2... то будет ли, грубо говоря, при каждом обращении этот
двойной оверхэд? И мне для ускорения стоит сделать что-то типа

struct med *localpb = idx->pb;
и дальше гнать уже
localpb->v...
localpb->v...

или, например, компилятор "сам такое делает"?

> и на самом деле у вас больший выбор:
это конечно. я сузил до двух приведённых вариантов, чтобы было о чём
предметно говорить.
> Выбор того или иного варианта при разработке зависит не только и не сколько от скорости/размера,
оно-то так это, но в данном конкретном случае у меня такая вот фантазия.
как связать "красиво", "удобно" и "предметно" я и так знаю :) а хоцца
так, чтобы быстро работало :))
--
antonvm
Reply | Threaded
Open this post in threaded view
|

Re[2]: доступ по указателю

Илья А. Коваленко
In reply to this post by Илья А. Коваленко

> Более конкретный вопрос такой: если происходит несколько обращений,
> либо к одной и той же idx->pb->v1, либо к некоторым idx->pb->v1,
> idx->pb->v2... то будет ли, грубо говоря, при каждом обращении этот
> двойной оверхэд? ...

однозначно будет двойной оверхед. многоуровневую косвенность компилятор не оптимизирует (AFAIK, во всяком случае)
BTW, вы всегда можете убедиться в этом самостоятельно, посмотрев получающийся ассемблерный код (gcc -S -o test.s test.c)

если вы хотите попасть под оптимизацию с бОльшей вероятностью, можно добавить register:

- struct med *localpb = idx->pb;
+ register struct med *localpb = idx->pb;
  localpb->v...
  localpb->v...

Reply | Threaded
Open this post in threaded view
|

Re: Re[2]: доступ по указателю

Anton Maksimenkov-2
> BTW, вы всегда можете убедиться в этом самостоятельно, посмотрев получающийся ассемблерный код (gcc -S -o test.s test.c)

Спасибо, это помогло.
--
antonvm
Reply | Threaded
Open this post in threaded view
|

Re: доступ по указателю

Andrew Jelly-2
In reply to this post by Anton Maksimenkov-2

On 01/12/10 14:29, Anton Maksimenkov wrote:

> Более конкретный вопрос такой: если происходит несколько обращений,
> либо к одной и той же idx->pb->v1, либо к некоторым idx->pb->v1,
> idx->pb->v2... то будет ли, грубо говоря, при каждом обращении этот
> двойной оверхэд? И мне для ускорения стоит сделать что-то типа

Двойной overhead будет только если имело место первое обращение.
Т.е. понадобилось загрузить в базовый регистр адрес подструктуры.
Дальше, если обращений несколько, компилятор не станет забывать
адрес подструктуры.

> struct med *localpb = idx->pb;
> и дальше гнать уже
> localpb->v...
> localpb->v...

> или, например, компилятор "сам такое делает"?

Да, делает, причем, как я вижу, даже без O3.
Вот пример листинга, тут:

     big *p_big;  - большая структура
     idx *p_idx;  - внешняя структура
     med *p_med;  - внутренняя структура

        mov eax, [esi+12]       ; грузим в eax адрес pm = p_idx->pm;
        mov [ebx+12], 1         ; p_big->v1=1;
        mov [eax+24], 2         ; p_idx->pm->v7=2;
        mov [eax+28], 2         ; p_idx->pm->v8=2;
        mov [ebx+48], 1         ; p_big->v10=1;
        mov [eax+32], 2         ; p_idx->pm->v9=2;
        mov [esi],    3         ; p_idx->uid=3;

Как видно, только при первом обращении к подструктуре, был вычислен ее
адрес. Более того, на других архитектурах процессоров может не быть и этого.

Причем, все нормально даже если мы смешиваем обращения к разным
структурам в С-шном коде. Пока регистров хватает, оптимизатор будет
стараться не забывать нужные адреса.

Иными словами - пусть код оптимизирует транслятор, а байты экономит
pklite. Алгоритмическая оптимизация гораздо важнее...

--
Local Observer

Reply | Threaded
Open this post in threaded view
|

Re: доступ по указателю

Anton Maksimenkov-2
1 декабря 2010 г. 22:29 пользователь Andrew Jelly
<[hidden email]> написал:
>> или, например, компилятор "сам такое делает"?
> Да, делает, причем, как я вижу, даже без O3.
> Как видно, только при первом обращении к подструктуре, был вычислен ее
> адрес. Более того, на других архитектурах процессоров может не быть и этого.

Я увидел не совсем так. Тока я извиняюсь, не расставил где что из
стека и остальное в асме.
(cc -O2 -pipe  ...)

void init (struct user *const user)
{
        ((struct user_info *)(user->ui))->a = 0;
        ((struct user_info *)(user->ui))->b = 0;
        ((struct user_info *)(user->ui))->c = 0;
        return;
}
генерится так:
init:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    108(%edx), %eax
    movl    $0, (%eax)
    movl    108(%edx), %eax
    movl    $0, 4(%eax)
    movl    108(%edx), %eax
    movl    $0, 8(%eax)
    popl    %ebp
    ret
А "ускоренная"
void init (struct user *const user)
{
        struct user_info *ui = (struct user_info *)user->ui;
        ui->a = 0;
        ui->b = 0;
        ui->c = 0;
        return;
}
генерится всё-таки вот этак:
init:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %eax
    movl    108(%eax), %eax
    movl    $0, (%eax)
    movl    $0, 4(%eax)
    movl    $0, 8(%eax)
    popl    %ebp
    ret


> Алгоритмическая оптимизация гораздо важнее...
Бесспорно.
Просто для одной из програмок, довольно тривиальной алгоритмически,
глодала мысль "а не получить ли скорость изменением структуры хранения
данных". Отсюда и началось.
--
antonvm
Reply | Threaded
Open this post in threaded view
|

Re[2]: доступ по указателю

Илья А. Коваленко
In reply to this post by Andrew Jelly-2

> mov eax, [esi+12]       ; грузим в eax адрес pm = p_idx->pm;
> mov [ebx+12], 1         ; p_big->v1=1;
> mov [eax+24], 2         ; p_idx->pm->v7=2;
> mov [eax+28], 2         ; p_idx->pm->v8=2;
> mov [ebx+48], 1         ; p_big->v10=1;
> mov [eax+32], 2         ; p_idx->pm->v9=2;
> mov [esi],    3         ; p_idx->uid=3;
>
> Как видно, только при первом обращении к подструктуре, был вычислен ее
> адрес.

Хмм, об этом я не подумал ... но не радовать это все равно не может, получается локальная переменная дефакто равнодоступна с членом произвольно вложенной структуры, забавно.

Reply | Threaded
Open this post in threaded view
|

Re: доступ по указателю

Pavel Labushev-3
In reply to this post by Anton Maksimenkov-2

> как связать "красиво", "удобно" и "предметно" я и так знаю :) а хоцца
> так, чтобы быстро работало :))

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