Как оптимизировать работу в данном случае?

← →
Cooller (2006-10-11 09:32) [0]

Есть серверное приложение (активная одновременная работа с 1000+ клиентами). Пишется "навес" ввиде DLL, перехватывающий и анализирующий весь входящий траффик (функции send/recv). Для каждого соединения необходимо хранить некую информацию:
TClientData=record ... end;
Уникальным идентификатором получается может быть только TSocket. Как быстро находить и изменять нужную информацию для каждого клиента? С одной стороны хорошо бы было использовать TSocket в качестве индекса. В модуле WinSock: TSocket = u_int;
Получается нужно объявить вот такой массив:
aClientData:array [integer] of TClientData
В итоге:
[Error] Unit1.pas(21): Data type too large: exceeds 2 GB
В принципе ничего удивительного

Можно конечно создать динамический массив:
aClientData:array of record s:integer; data:TClientData; end;
Но при получении каждого пакета производить поиск по такому массиву - слишком накладное занятие (повторюсь - активная одновременная работа с 1000+ клиентами).

Как быть, что посоветуете?

← →
MBo © (2006-10-11 09:38) [1]

1. хэширование
2. дерево поиска (простое бинарное, красно-черное, AVL)
3. сортированный по ключу поиска массив + бинарный поиск

← →
Cooller (2006-10-11 10:10) [2]

2 MBo
Насколько сложный алгоритм необходимо использовать в данном случае? Номера назначаются сокетам по порядку или абсолютно случайно?
К примеру может ли подойти такой метод?
function FindSock(s:TSocket):integer; var i:0..$FFFF; begin Result:=-1; i:=s mod $FFFF; while aCD[i].s<>0 do begin if aCD[i].s=s then begin Result:=i; break; end; i:=i-1; end; end; function AddSock(s:TSocket):integer; var i:0..$FFFF; begin Result:=-1; i:=s mod $FFFF; while aCD[i].s<>0 do begin if aCD[i].s=s then begin Result:=i; exit; end; i:=i-1; end; result:=i; end;

← →
Сергей М. © (2006-10-11 10:20) [3]

> входящий траффик (функции send/recv)

Send - это исходящий траффик.

> производить поиск по такому массиву - слишком накладное
> занятие

Немногим накладнее чем при стат.массиве.

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

← →
Сергей М. © (2006-10-11 10:22) [4]

> Номера назначаются сокетам по порядку или абсолютно случайно?

Неважно как они назначаются, никаких предположений на эту тему делать не следует.

Важно чтобы на момент необходимости поиска эти "номера" были упорядочены.

← →
MBo © (2006-10-11 10:24) [5]

>Номера назначаются сокетам по порядку или абсолютно случайно?
Этого я не знаю.
В примере ты используешь простейшее хэширование по младшему слову и линейный поиск. Это будет приводить к конфликтам, да и поиск медленный, так что лучше все же использовать настояще хэширование, исходники найти нетрудно.
Принцип - заводится массив размером N раза в полтора больше количества ключей
Ключ (у тебя номер сокета) хэшируется - по некоему алгоритму кодируется, приводится к диапазону 0..N-1
Поиск требует очень малого количества операций - обычно одну, при возможных конфликтах (которые разруливаются хэш-алгоритмом) - пару-тройку, добавление - тоже.

← →
Cooller (2006-10-11 10:35) [6]

В итоге есть два метода реализации:
1. Использовать динамический массив. При добавлении нового сокета - вставлять его в нужную ячейку, чтобы список был упорядоченным (как это реализовать? move?)

2. Использовать статический массив и хеширование (сейчас займусь поиском исходников).

Какой вариант выбрали бы Вы?

← →
Cooller (2006-10-11 10:38) [7]

Мне кажется, что хеширование выиграет в скорости

← →
Cooller (2006-10-11 10:46) [8]

И какой алгоритм хеширования посоветуете (чтобы бы проще искать)?

← →
Сергей М. © (2006-10-11 10:55) [9]

3. Использовать TList

← →
Cooller (2006-10-11 11:34) [10]

> 3. Использовать TList

А как обстоят дела с быстродействием?
---
Вообщем мне надо выбрать и трёх вариантов =)

← →
Сергей М. © (2006-10-11 11:58) [11]

> как обстоят дела с быстродействием?

Дело не в быстродействии (оно сравнимо с вариантом для стат.массива), а в удобстве.

TList имеет готовый метод Sort, реализующий алгоритм быстрой сортировки списка.

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

← →
Cooller (2006-10-11 12:04) [12]

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

← →
Сергей М. © (2006-10-11 12:14) [13]

> выбора алгоритма имеет огромное значение

Конечно имеет.
Но ведь вопрос твой был не о выборе алгоритма поиска в упорядоченном списке, а об организации такого списка ...

← →
MBo © (2006-10-11 13:09) [14]

Если добавление/удаление элементов происходит часто, лучше деревом или хэшем воспользоваться.

← →
Cooller (2006-10-11 13:10) [15]

Добавление и удаление очень редко. Соединение в среднем длится около часа.

← →
atruhin © (2006-10-11 14:41) [16]

А не проще создать прямой массив array [0..65535] of word; всего 128 кб для севрера не так много, зато ни какого поиска.

← →
Сергей М. © (2006-10-11 14:51) [17]

> atruhin © (11.10.06 14:41) [16]

И нафиг он нужен, этот массив слов ? С какого боку его к теме автора присандалить ?

← →
atruhin © (2006-10-11 15:16) [18]

> [17] Сергей М. © (11.10.06 14:51)

Да тут ошибся. array [0..65535] of PaClientData; 256кб. Если это допустимо, по расходу памяти, то самый простой и быстрый вариант.

← →
Сергей М. © (2006-10-11 15:21) [19]

> atruhin © (11.10.06 15:16) [18]

При заданных автором условиях - не согласен.

← →
Cooller (2006-10-11 15:34) [20]

2atruhin
Socket - U_INT (0..$FFFFFFFF)

← →
Cooller (2006-10-11 15:37) [21]

А так памяти оперативной достаточно - 4Гб

← →
Сергей М. © (2006-10-11 15:39) [22]

> Cooller (11.10.06 15:34) [20]

Боюсь, ты упускаешь из виду самое главное - мультипоточность сервера.

← →
Cooller (2006-10-11 16:07) [23]

2 Сергей М
А в чем именно загвоздка?

В том что перехватываемые тобой send/recv-ф-ции могут вызываться из разных кодовых потоков.

ещё можно "корзинки" использовать -- array [0..255] of array [...] of ... %-)

зыж номера сокетам назначаются не всегда "по-порядку". помедитируй над исходниками wsock.

← →
Cooller (2006-10-11 17:25) [26]

Еще вопрос... Сервер 64х разрядный и работает в 64х разрядной системе. Надо ли это учитывать при перехвате send/recv?

function MyRecv(s: TSocket; var Buf; len, flags: Integer): Integer; stdcall;

> Надо ли это учитывать при перехвате send/recv?

Надо, если ОС имеет соотв.разрядность

← →
Cooller (2006-10-11 17:34) [28]

Чувствую тут возникнет путаница...

Получается заголовок будет такой?
function MyRecv(s: int64; var Buf; len, flags: in64): int64; stdcall;
Или я сейчас бред написал? =)

> Cooller (11.10.06 17:34) [28]

ОС какая ?

← →
Cooller (2006-10-11 17:40) [30]

Windows 2003 Server 64

значит ищи заголовочные файлы для ws2_64.dll (или как ее там для 64-разрядной версии зовут - не в курсе)

← →
Cooller (2006-10-11 18:25) [32]

А вообще 32х разрядная библиотека сможет нормально функционировать в 64х разрядном приложении?

← →
Cooller (2006-10-11 20:33) [33]

Вот к примеру:
function MyRecv(s: TSocket; var Buf; len, flags: Integer): Integer; stdcall;

Если память уже 64х разрядная, то указатель buf также 64х разрядный. В Delphi это ведь никак не реализовать...

Как оптимизировать работу в данном случае? Найти похожие ветки