OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 15 Сентябрь, 2019 13:19

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 15:15 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
PGR писал(а):
Большое спасибо за ссылку! С удовольствием почитал. Сколько лет писал на Delphi, а про такие тонкости не знал (всегда пользовался AnsiString, изредка - ShortString).
Valery Solovey писал(а):
По-моему, это не то, Что искал Александр. Его, скорее, интересовали принципы, а не использование конкретных инструментов конкретного языка.
Тем не менее, основной круг проблем там очерчен и основные подходы (нуль-терминированные, с известной длиной и комбинированный тип) рассмотрены. Как видно, поддержка со стороны компилятора там нехилая. Не знал, что PChar - это не просто ^Char.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 15:25 

Зарегистрирован: Понедельник, 19 Март, 2007 09:40
Сообщения: 142
Откуда: USA, Israel, Belarus
Если приходится знать, какая именно реализация string используется даже в простейших случаях, и "иногда" переходить на better_string, то это и есть Lack of Abstraction.
Если string позволяет гулять по памяти -- это и есть главный дефект к интерфейсу/дизайну и т.д.
Хотели optimization and backward compatibility -- получаем дырки в системе.

И зная все недостатки C++ и STL, Вы ЭТО приводите как эталон для подражания?

На все недостатки, что есть в строках Oberon, главное достоинство -- минимализм и простота.
Не все случаи покрывает, но как видно проблема не тривиальна.
И вместо того, что бы наворотить как в STL с кучай дырок, реализованы простые безопасные строки.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 15:57 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Мне так представляется, что тип AnsiString близок к оптимуму по соотношению цена/качество. Связанные с ним проблемы, описанные в статье, начинаются при попытке состыковать его с другими типами - ShortString и PChar, а точнее - при попытке обеспечить максимально прозрачную совместимость с ними.

В этой связи мне интересно вот что: можно ли реализовать подобный тип в библиотеке на Обероне? Как счётчик ссылок увязать со встроенной сборкой мусора? Или при наличии сборки от счётчика можно отказаться? Счётчик удобен при присваивании (создании точной копии) строки: копирование содержимого откладывается до момента реальной необходимости. Без счётчика не ясно, когда нужно выполнить UniqueString. Какие проблемы могут возникнуть при взаимодействии со стандартными ARRAY OF CHAR?

Мне интересно вот почему: в Amadeus есть тип Str.PStr и куча разных процедур типа Str.Append, Str.AppendIfNone и прочих. Если грамотно продумать этот тип, внедрить его повсеместно, а потом собрать статистику, какие операции выполняются чаще всего и занимают больше всего времени, то можно очень хорошо оптимизировать это дело.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 16:13 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
slava писал(а):
Если приходится знать, какая именно реализация string используется даже в простейших случаях, и "иногда" переходить на better_string, то это и есть Lack of Abstraction.


Как раз особенности реализации std::string никого не волнуют. Наоборот, по факту эти реализации отличаются даже на одной платформе/компиляторе, поэтому желания вникать в реализацию, использовать недокументированные фичи и чего-то там хэкать - не возникает. Переходить на better_string никто вас не заставит, кроме профайлера. Используйте стандартную строку со стандартным поведением - и будет вам счастье.

slava писал(а):
Если string позволяет гулять по памяти -- это и есть главный дефект к интерфейсу/дизайну и т.д.


Дизайн std::string не позволяет гулять по памяти. Гулять по памяти вам позволяет адресная арифметика C++.

slava писал(а):
Хотели optimization and backward compatibility -- получаем дырки в системе.


Это вы про метод .c_str()? Ну так не вызывайте его и не будет у вас дырок. Неявно этот метод вызвать нельзя. Он нужен только для сишного API с его нулевым символом на конце. Если вы на обероне захотите вызвать сишное API, то получите точно такую же дырку.

slava писал(а):
И зная все недостатки C++ и STL, Вы ЭТО приводите как эталон для подражания?


Да. У std::string вполне вменяемая концепция, в отличие от обероновских строк. std::string можно нормально присваваивать, складывать, возвращать и не думать о нулевом символе и прочих трапах.

slava писал(а):
На все недостатки, что есть в строках Oberon, главное достоинство -- минимализм и простота.


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 16:39 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Александр Ильин писал(а):
В этой связи мне интересно вот что: можно ли реализовать подобный тип в библиотеке на Обероне? Как счётчик ссылок увязать со встроенной сборкой мусора? Или при наличии сборки от счётчика можно отказаться?


Естественно. Не нужен вам никакой счетчик ссылок. Извинте, напишу прототип на C++, но вы поймете:

Код:
struct string
{
char *data; // Указатель на открытый массив, GC разберется с его временем жизни
};

void
assign( string& s1, sting& s2 )
 {
    s1.data = s2.data; // обе строки шарят общие данные, память не перевыделяется
 }

void
append( string& s1, string&s2 )
{
    char* new_data = allocate(s1.size() + s2.size()); // строка модифицируется, поэтому перевыделяем память под нее
    copy( new_data, 0, s1.data );
    copy( new_data, s1.data.size(), s2.data );
    s1.data = new_data;
}


P.S. Хотя я бы предложил вам рассмотреть вариант просто константной строки, без операций модификации (append). Ее реализация тривиальна и эффективна, плюс дополнительный constraint в случае интерфейса.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 16:57 

Зарегистрирован: Понедельник, 19 Март, 2007 09:40
Сообщения: 142
Откуда: USA, Israel, Belarus
К сожалению, STL'евский operator[], не проверяет выход за диапазон.
Реализацию STL не нужно знать, если программируешь на прикладном уровне, а если -- на системном, то приходится влазить и "пачкаться".
Во многих простых случаях string оказывается просто не подходящим (слишком тяжеловестным).
Добавлю: неортоганальность string и stringstream (и там и там, есть конкатенация строк).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 17:06 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
slava писал(а):
К сожалению, STL'евский operator[], не проверяет выход за диапазон.


Если кому-то нужна проверка на диапазон - он использует at(). Я, например, вообще практически не использую ни operator[] ни at() при работе со строками. Поэтому и проблема проверок выхода за диапазон меня волнует мало...

slava писал(а):
Реализацию STL не нужно знать, если программируешь на прикладном уровне, а если -- на системном, то приходится влазить и "пачкаться".


Если кому-то приходится - то он ССЗБ. Покажите пример "системного" кода где приходится "пачкаться".

slava писал(а):
Во многих простых случаях string оказывается просто не подходящим (слишком тяжеловестным).


Например?

slava писал(а):
Добавлю: неортоганальность string и stringstream (и там и там, есть конкатенация строк).


Я не очень понял, что именно вы имеете ввиду. Это все претензии к дизайну std::string?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 17:55 

Зарегистрирован: Понедельник, 19 Март, 2007 09:40
Сообщения: 142
Откуда: USA, Israel, Belarus
Vlad писал(а):
slava писал(а):
К сожалению, STL'евский operator[], не проверяет выход за диапазон.
Если кому-то нужна проверка на диапазон - он использует at(). Я, например, вообще практически не использую ни operator[] ни at() при работе со строками. Поэтому и проблема проверок выхода за диапазон меня волнует мало...
Все алгоритмы copy, sort и т.д. не проверяют корректность итераторов, так что Вы тоже ходите по минному полю :wink:

PS использование иногда [], а иногда at() -- Leak of Abstraction.
Психологический фактор, програмеры почти всегда используют [], можно обвинять людей, но я вижу это как проблему в STL.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Вторник, 09 Сентябрь, 2008 18:32 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
slava писал(а):
Все алгоритмы copy, sort и т.д. не проверяют корректность итераторов


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

slava писал(а):
, так что Вы тоже ходите по минному полю :wink:


Отнюдь. У нас все стандартные алгоритмы имеет версию с последовательностью на входе, а-ля:
Код:
template <typename Sequence, typename Pred>
void
for_each(const S &s, Pred p)
{
    std::for_each(s.begin(), s.end(), p);
}


Получить в таком случае некорректный итератор очень сложно.

slava писал(а):
PS использование иногда [], а иногда at() -- Leak of Abstraction.


Нет. Это свобода выбора - с проверкой или без.

slava писал(а):
Психологический фактор, програмеры почти всегда используют [], можно обвинять людей, но я вижу это как проблему в STL.


Да, "по умолчанию" используется самый удобный и эффективный вариант. Вполне нормальное "умолчание" для языке с претензией на максимальную эффективность. Вы готовы жертвовать эффективностью ради безопасности - используйте другой язык с другими "умолчаниями".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Среда, 10 Сентябрь, 2008 19:02 

Зарегистрирован: Вторник, 27 Ноябрь, 2007 20:40
Сообщения: 48
[size=50]
Valery Solovey писал(а):
Александр Ильин писал(а):
...

Да, интересная тема и ссылки. У меня тоже были сомнения - как же лучше организовать работу со строками?
Сначала в BB, потом в XDS, потом при попытке добиться переносимости (BB<->XDS) за счёт промежуточных базовых типов (модуль MyType) и двух версий библиотек...

Пока остановился на варианте строк (тип VSTR) с тремя реквизитами: V - указатель на область, J - индекс, L - длина.
Основной набор символов - CP1251, по 1 байту на символ. Другие кодировки - через конвертеры.

Для VSTR можно легко определять подстроки и работать с ними теми же функциями. Не нужно перемещать указатель. Можно работать с данными где они лежат...

На мой взгляд такие строки - в первом приближении - вполне приемлемый компромис для различных применений.
Для примера ББ версия модуля MyType:
[size=50]MODULE MyType;
TYPE
BOOL* = BOOLEAN;
(***BYTE* = BYTE; ***)
CH1* = SHORTCHAR;
CH2* = CHAR;
CH* = CH1; (* DEFAULT *)
INT1* = BYTE;
INT2* = SHORTINT;
INT4* = INTEGER;
INT8* = LONGINT;
INT* = INT4; (* DEFAULT *)
FLOAT4* = SHORTREAL;
FLOAT8* = REAL;
FLOAT* = FLOAT8; (* DEFAULT *)

STR1* = ARRAY OF CH1;
PSTR1* = POINTER TO STR1;
STR2* = ARRAY OF CH2;
PSTR2* = POINTER TO STR2;
STR* = ARRAY OF CH; (* DEFAULT *)
PSTR* = POINTER TO STR;
BUF* = ARRAY OF BYTE;
PBUF* = POINTER TO BUF;

VSTR* = RECORD V*: PSTR; J*, L*: INT; END; (*// DEFAULT *)
A_VSTR* = RECORD A*: POINTER TO ARRAY OF VSTR; N*: INT; END;

END MyType.
[/size]


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Среда, 15 Октябрь, 2008 08:00 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Критика строк в Модула/Оберон/КП: http://z505.com/cgi-bin/qkcont/qkcont.c ... n%20Quiche


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Среда, 15 Октябрь, 2008 11:00 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8174
Откуда: Троицк, Москва
Александр Ильин писал(а):
Критика строк в Модула/Оберон/КП: http://z505.com/cgi-bin/qkcont/qkcont.c ... n%20Quiche

Если вдуматься, это не "Критика строк в ...", потому что по определению/смыслу/идеологии этих языков всё, что требует динамического управления памятью, отправляется в библиотеки.

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

Выходит, это либо критика самой идеологии, либо критика библиотек.

Подумавши, заключаем, что Вирт опять был прав :-)
----------------------
Кстати, почему тему нельзя так и назвать, ПРО СТРОКИ.
Неправильная манера -- то Веселовский, то Сполски...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Четверг, 16 Октябрь, 2008 10:29 

Зарегистрирован: Четверг, 16 Октябрь, 2008 10:27
Сообщения: 3
From the frustrated and stressed PasWiki Author:

Why does Component Pascal use '$' dollar sign. Why not put this in the library?

"Note that the language Component Pascal provides efficient built-in support for string assignment (implicitly or explicitly with the "$" operator),"

Not everything can be elegantly placed into a library...

Show me how to use Oberon/Modula "strings" elegantly.... ? Where are some libraries we can use?

Код:
MODULE AnsiString
...
...// insert the implementation here
...// is this an Extended Record?
...// what about operator overloading + for concatenation
...// is an AnsiString ever possible in a Library (module) ??
END.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Четверг, 16 Октябрь, 2008 11:41 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8174
Откуда: Троицк, Москва
L505 писал(а):
From the frustrated and stressed PasWiki Author:
Why does Component Pascal use '$' dollar sign. Why not put this in the library?

Nice to have you with us!

A library would probably emerge when someone really needs it.

The simple CP conventions seem to be convenient for small string-related tasks, such tasks pop up everywhere.
And for complicated text processing there is TextModels.Model.
This perhaps explains why no one has written a string library beyond what's available in the BlackBox's Strings module.


Последний раз редактировалось Info21 Четверг, 16 Октябрь, 2008 19:44, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Четверг, 16 Октябрь, 2008 17:05 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
L505 писал(а):
Why does Component Pascal use '$' dollar sign. Why not put this in the library?
Well, I can't say for the entire BlackBox community, but when I switched to XDS/Amadeus I found the Str module with lots of string-related procedures (both dynamically allocated and stack-based). I guess that introduction of '$' in CP sort of dissolves the need for a library, makes it less evident. I don't know if an elegant solution is possible, because the Str currently deals with all sorts of Oberon strings instead of providing an abstract data type. When (and if) I introduce such a type and convert the Amadeus to use it throughout the library, then I'll see if it truly would be better to have it in the compiler (as it is in Delphi).

Operator overloading by a library is not supported, only procedures/methods. I'm 100% sure the library for AnsiString is possible, although it would rely on GC, not reference counting.

BTW, I got interested but didn't find CapString implementation in your SVN (the link only leads to a test module).

PS: You are welcome! What does "L505" mean?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Пятница, 17 Октябрь, 2008 10:55 

Зарегистрирован: Четверг, 16 Октябрь, 2008 10:27
Сообщения: 3
I would love to see an ansistring module prototype (even if it is half broken and incomplete) for Oberon/ComponentPascal.
I do not know how concatenations will be easy to do, with regards to the plus sign? For example:

Код:
  SomeString + SomeOtherString


The "library" way that I know of looks like this....

Код:
SomeString.Concatenate(SomeOther)


and how about indexed access to the string, such as

Код:
SomeString[12]


Must one use

Код:
SomeString.Index(12)


How about range index access

Код:
SomeString[1..13]


CapString is somewhere on SVN in the folders above the demo.. I will try find it. I got discouraged when I quickly figured out that CapString is something that needs to be implemented at the compiler level. Same with CapArray. The only option I could think of was an Object of some sort. But I do not like Freeing and Creating objects... it ruins the whole cleanliness of code. So again I simply got discouraged with modern pascal (delphi and fpc) due to the language always requiring modifications to the compiler!

By the way "Tutorial Dee" for database programming seems to solve the "Types" problem by suggesting an extensive operator overloading system... so that people can create new types without extending the compiler so much (create restrictive types according to what the programmer demands). However, I cannot imagine how complex Tutorial Dee will turn out, nor do I know if Tutorial Dee in its entirety is even possible (it is mostly a theory language by Darwin and Date). But once again I do not think Date and Darwin even address Strings a whole lot in their literature.

My name? is random. 505 is just a number I picked to identify myself.. kind of like 007 with James Bond I guess.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Пятница, 17 Октябрь, 2008 11:00 

Зарегистрирован: Четверг, 16 Октябрь, 2008 10:27
Сообщения: 3
What is XDS/Amadeus .. ?

By the way, sorry for not being a good Russian person speaking Russian language, haha. I ruin the culture here with English!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Пятница, 17 Октябрь, 2008 11:55 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
L505 писал(а):
What is XDS/Amadeus .. ?
XDS is a Modula[-2]/Oberon[-2] optimising compiler for Windows/Linux. It used to be commercial, but now it's freeware. http://www.excelsior-usa.com/xdsx86.html
Amadeus-3 is a commercial GUI library by Stefan Metzeler (CEO "Amadeus IT Solutions"). It is written in Oberon-2 (previously in Modula) and used as a core in multiple applications for Windows. It provides DB access, reporting capabilities, partial OS abstraction, etc.
L505 писал(а):
By the way, sorry for not being a good Russian person speaking Russian language, haha. I ruin the culture here with English!
No need to apologize, just try to enrich the culture instead : )


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Пятница, 09 Январь, 2009 16:49 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Vlad писал(а):
Забить на статические массивы и использовать нормальные динамические строки :) В библиотеке. Как это сделали в C++ ;)
И в Delphi.

Я решил-таки сделать нормальную библиотеку для работы с динамическими строками. Естественно, разработка ведётся под XDS. По реализации выглядит примерно так: библиотека Strings, абстрактный тип Strings.Str. Реализация скрыта в типе Strings.Str2, расширении Str.

Я решил совместить подход Delphi (AnsiString со счётчиком ссылок) и ОС Oberon (со сборщиком мусора). Сделал так: строка - это цепочка записей типа Str2, связанная через поля next и prev. Данные хранятся не в Str2, а в отдельном типе Piece, в поле data:
Код:
CONST
   PieceSize = 127;
TYPE
   Piece = POINTER TO RECORD
      ref: INTEGER;
      data: ARRAY PieceSize OF CHAR;
   END;
   Str* = POINTER TO ABSTRACT RECORD
   END;
   Str2 = POINTER TO RECORD (Str)
      piece: Piece;
      beg, end: BYTE;
      prev, next: Str2
   END;
Piece.ref - это счётчик ссылок. Блоки Piece.data являются разделяемыми: на один и тот же блок может ссылаться несколько строк. Таким образом, копирование строки, разделение строк на несколько частей, удаление части, конкатенация - всё это не приводит к дублированию данных, а только к созданию цепочек ссылок из Str2 на уже существующие блоки, и увеличению их piece.ref. Уменьшается piece.ref либо при удалении куска строки, либо в финализаторе корневого Str2.

Зачем вообще нужен Piece? Почему не реализовать всё через POINTER TO ARRAY OF CHAR произвольной длины? Piece нужен ради Piece.ref, т.е. для подсчёта ссылок на Piece.data. Подсчёт ссылок, в свою очередь, нужен для того, чтобы при модификации содержимого строки можно было узнать, экслюзивно ли строка владеет данным блоком или нет, и если нет, то сделать себе отдельную копию. Если эксклюзивно, то копию делать не нужно. Если данные не модифицируются, то и копирования не происходит, только создаются дополнительные управляющие структуры. При PieceSize = 127 оверхед на управляющие структуры (цепочки из объектов Str2) составляет около 33%, т.е. на строку длиной 10Мб данных надо дополнительно разместить 3.3Мб объектов Str2/Piece.

Почему Piece.data имеет фиксированный размер? Это вопрос сложный, равно как и выбор значения PieceSize. С одной стороны, хочется избежать ситуации, когда управляющие структуры занимают в памяти больше места, чем полезный объём строки. С другой стороны, не хочется слишком раздувать минимальный размер строки. С третьей стороны, если Piece.data будет не ARRAY, а POINTER TO ARRAY динамического размера, то это дополнительно нагрузит сборщик мусора. Очень хотелось бы услышать альтернативные предложения или почитать что-то на эту тему. В настоящее время я подумываю о том, чтобы сделать собственный небольшой менеджер памяти, который бы брал память непосредственно у ОС. При фиксированном размере блока это тривиальная задача на один вечер. При наличии собственного менеджера, в памяти GC будут выделяться только управляющие структуры Str2, а полезные данные вместе со счётчиками ссылок будут размещаться в дополнительной, специально выделенной памяти. Счётчики ссылок позволят повторно использовать блоки, на которые больше нет ссылок из управляющих структур. При этом, ввиду фиксированного размера, поиск свободного блока будет происходить очень быстро. В памяти GC же будут выделяться только маленькие кусочки, что снизит фрагментацию. Плюс, собственный менеджер памяти позволит увидеть, насколько память нагружена строковыми данными, да и вообще даст некоторые показатели здоровья приложения.

Поля Str2.beg и Str2.end обозначают область piece.data [beg..end-1], используемую данным экземпляром Str2. Таким образом, длина строки вычисляется так:
Код:
PROCEDURE Length* (s: Str): LONGINT;
(** Return the number of characters in 's'. If 's' = NIL, return 0.
  * Pre: (s = NIL) OR (s IS Str2), guarded
  * Post: result >= 0, 60 *)
VAR
   s2: Str2;
   res: LONGINT;
BEGIN
   (* Implementation note: the current algorithm shows performance increase of
    * up to 42 times as compared to the linear 0X search for regular Oberon
    * strings. Still, since all string operations are encapsulated in this
    * module, it is possible to maintain current length of a string in a
    * hidden field for completely instant retrieval. *)
   res := 0;
   IF s # NIL THEN
      s2 := s (Str2);
      IF s2.piece # NIL THEN
         WHILE s2 # NIL DO
            INC (res, s2.end - s2.beg);
            s2 := s2.next;
         END;
      END;
   END;
   ASSERT (res >= 0, 60);
   RETURN res
END Length;
Для конвертации из обычного символьного массива в Strings.Str и обратно используются следующие процедуры:
PROCEDURE Assign* (VAR s: ARRAY OF CHAR; VAR str: Str);
PROCEDURE Get* (src: Str; VAR dst: ARRAY OF CHAR);
Assign берёт данные из s до 0X, т.е. работает с обычными Oberon-строками, например, создаваемыми компилятором текстовыми константами. Get добавляет в конец экспортированного содержимого символ 0X, например, для последующей передачи в фукнцию ОС или другую Oberon-строку.

Поскольку строки реализованы в виде списков, наиболее эффективными в качестве базисных операций оказались следующие: Split, Join, Copy
Код:
PROCEDURE Split* (str: Str; at: LONGINT): Str;
(** Split the 'str' in two. str [at] is the first character of the new string.
  * Pre: 0 <= at, 20
  * Pre: at < Length (str), 21 or NIL dereference trap
  * Post: Length (result) = Length (str) - at > 0
  * Post: Length (str) = at *)
PROCEDURE Join* (VAR str: Str; tail: Str);
(** Move 'tail's contents to the end of 'str' and empty 'tail'. If 'tail' =
  * NIL, do nothing. Split and Join are mutually inverse operations on the
  * contents: Join (str, Split (str, x)) = str, where 0 <= x < Length (str).
  * Post: str # NIL
  * Post: Length (str') = Length (str) + Length (tail)
  * Post: Length (tail) = 0 *)
PROCEDURE Copy* (src: Str; VAR dst: Str);
(** Copy the entire contents of string 'src' into 'dst'. Prefer creating cheap
  * copy of the string, i.e. with as little data moving overhead as possible.
  * The operation logic of the procedure depending on the parameters is guided
  * by the following table:
  *     src   dst
  * 1)  NIL   NIL - do nothing, the strings are already equal;
  * 2)  NIL  #NIL - set 'dst' = empty string (Length (dst) = 0);
  * 3) #NIL   NIL - create 'dst' and copy contents from 'src';
  * 4) #NIL  #NIL - if (src = dst), do nothing, otherwise replace the current
  *                 contents of 'dst' with the contents of 'src'.
  * Only in case 3) the value of the 'dst' variable will be replaced,
  * otherwise it is preserved, as there may be other references to the string
  * object in the client code. If 'src' is empty in case 3), the new empty 'dst'
  * is created.
  * Post: dst is a valid string, 60
  * Post: Length (src) = Length (dst), 61 *)
Для индексированного доступа к содержимому собираюсь сделать Reader и Writer по образцу ОС Oberon. Благодаря инкапсуляции доступа к содержимому строк, надеюсь в этом году перевести Amadeus на Unicode.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Джоэл Сполски, Назад, к основам
СообщениеДобавлено: Пятница, 09 Январь, 2009 23:57 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4489
Откуда: Россия, Орёл
Александр Ильин писал(а):
Счётчики ссылок позволят повторно использовать блоки, на которые больше нет ссылок из управляющих структур. При этом, ввиду фиксированного размера, поиск свободного блока будет происходить очень быстро.
Что Вы скажете про подход, указанный у Кнута в разделе про списки. Выделенный у системы блок памяти превращается в односвязный список L свободных Piece. При выделении блоки удаляются из начала L, при освобождении по ref = 0 блоки добавляются в начало L.

Плюс: поиск свободного блока за фикс. время
Минус: еще один вспом-й ук-ль.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB