Re: [fpc-devel] TList or TFPList - a Linked list ?
Micha Nelissen wrote: Hi, I've been thinking about adding a linked list implementation to either TList or TFPList. The basic problem to that is of course 1) space overhead of linked list is quite large 2) Index[..] will be O(N) For (1) I was thinking about making a linked list of an array of items, for example 14 pointers (so that 8 bytes are left for next pointer and memory manager needs on 32 bit platform). To solve (2), we can make the observation that generally people access lists in a linear fashion, and we might cache the previous and next list entry. The big advantage is getting rid of the many reallocs needed to grow the lists, because one usually doesn't set Capacity in advance, but keeps adding items until done. Using aggregation possibly, TStringList must benefit from it too. What do you think about it ? Micha ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc- My most recent project at work involves a good deal of non-linear access to TList items (sorry, not Free Pascal g), and this implementation would essentially kill the efficiency gains that we achieved by doing so. In addition, the caching overhead (the last requested index, as well as next prev pointers, and corresponding logic) would blow away the efficiency of iterating through TList items. There's no way to work around that. Linked lists are very specialized, and definitely have their place, and classes should be built for them. However, they're definitely their own beast, and should be treated as such. For instance, you made the valid point that they grow very easily and without the overhead of having to find large contiguous chunks of memory when the list grows, but iterating them is relatively slow. Programmers just need to recognize when this is an advantage and when it isn't. Just my $0.02. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] TList or TFPList - a Linked list ?
Michael Van Canneyt wrote: People that have large lists know this and take care of it. What is more, I think that 1 large memory block (an array) is much more efficient memory wise than many small blocks. This is true in some cases; VMs and scripting engines (such as SpiderMonkey) use this technique. However, when the list size is underestimated and has to grow it can be a huge detriment to performance and memory efficiency. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] TList or TFPList - a Linked list ?
Mattias Gaertner wrote: Your trick will only give a constant factor on growing/shrinking the list memory, gives an extra O(n) factor for sorting a TList, the caching costs time, and the memory usage will also grow. Just saw this last statement. The memory usage is very comparable to TList, even with bi-directional (doubly-linked) lists, since TLists tend to grow by leaps. For example, assuming a linked list item comprises of only a "next" pointer, it requires 8 bytes of memory (4 for the structure itself, 4 for the next pointer). In this case, 10,000 entries occupy 80,008 bytes (80,000 + 4 for pointer to First + 4 for pointer to Last), distributed around the memory table. Also keep in mind that the data payload for the linked list item is usually contained within the structure itself. A TList (stripped down for this case) requires 4 bytes for the list allocation, plus 4 bytes per list entry. 10,000 entries occupy 80,004 bytes. Now, two things: 1. With automatically growing lists you have a very high likelihood of unused pointers, so while a linked list of 10,000 items is utilizing all 80,004 bytes of memory, the TList allocated (10,000-TList.Count)*4 unused bytes of memory. 2. The TList entry only points to the actual data payload, meaning another 4+n bytes must be allocated to store the data. This means an additional 40,000 bytes is required for a TList vs. a linked list. On the other hand, this is equalized in a doubly-linked list. Disclaimer: this is all based on the Delphi implementation of TList, and may differ slightly (but probably not much) for the FP lists. Sterling ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] TList or TFPList - a Linked list ?
Mattias Gaertner wrote: Plus some bytes for the memory manager for each mem block. Typically 8. Forgot about that, sorry. In any case, the math still works. I'll explain. In this case, 10,000 entries occupy 80,008 bytes (80,000 + 4 for pointer to First + 4 for pointer to Last), ~160,000 distributed around the memory table. Also keep in mind that the data payload for the linked list item is usually contained within the structure itself. A TList (stripped down for this case) requires 4 bytes for the list allocation, plus 4 bytes per list entry. 10,000 entries occupy 80,004 bytes. ~40,000 Actually, if you account for the allocation of each of the 10,000 items added to the TList, it is ~120,000 (4 + 8 for memory manager that you pointed out above) plus the 40,000, bringing the total to 160,000. My point above is that the linked list item itself typically houses the payload, so no additional pointer allocation (or memory manager record) is required. Now, two things: 1. With automatically growing lists you have a very high likelihood of unused pointers, so while a linked list of 10,000 items is utilizing all 80,004 bytes of memory, the TList allocated (10,000-TList.Count)*4 unused bytes of memory. i.e. plus a maximum of 25% with the current implementation ~50,000 2. The TList entry only points to the actual data payload, meaning another 4+n bytes must be allocated to store the data. This means an additional 40,000 bytes is required for a TList vs. a linked list. Huh? Here I'm pointing out that the item each entry in the TList refers to has to be allocated somewhere. Best case scenario, a record, means a minimum of 4 bytes for each allocation, plus 8 for the memory manager. It all adds up. The main problem is the mem fragmentation. Here a growing TList can need up to 4 times its used memory. So in worst case it will need the memory of a single linked list. Regarding fragmentation, it's my personal experience that allocation of large numbers (millions) of small data packets is easier to manage in a suitably unpredictable environment. In cases where I need TList functionality, I really have to estimate (in my case at run-time, which is very hit-and-miss) how large to make the TList. If I mispredict then I chew up large chunks of contiguous memory very very quickly. If I overpredict, which usually happens by very large amounts, I'm wasting memory. Granted that's not a huge issue on servers with four gigabytes of RAM, but on these high-traffic servers it could be. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] TList or TFPList - a Linked list ?
Mattias Gaertner wrote: If the linked list item contains the whole data, then you are either not talking of the generic list this thread is about, or you use templates. In the later case a TList will also use templates and the 'payload' is the same. That's true of records, sure. Someone could also create a TLinkedListItem base class from which to descend and store their data there. The next prev pointers can be stored in the base class. Anyway, thanks for the discussion :) ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] TList or TFPList - a Linked list ?
Mattias Gaertner wrote: Well, if you use objects, then you get even more mem overhead ... :) I was thinking about that too. Then, IIRC, I read that object overhead is a one-time allocation of class tables and such. Of course, you might have some extra overhead inherited from TObject (ClassName etc). In my case, though, I use TList for objects anyway, so it all balances out. Guess it really depends on how one uses the tools. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Patch for bug 3774
In reply to Thomas Schatzl: Another optimization for your patch is to set a var to length(s) at the beginning of the proc, and use the var instead. It's called often enough that a little time could be shaved off.Post your free ad now! Yahoo! Canada Personals___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
[fpc-devel] Patch for bug 2453
(My ISP's mail server is blacklisted, so sending this from Yahoo. Ugh.)
This is my first shot, so be gentle :-)
The patch assumes FP wantscompatibility with BP 7. If so, it fixes two problems; if not, at least it was a fun exercise.
First, BP ignores non-numeric characters when a ReadLn is called with an integer parameter. To fix this, I changed ReadNumeric's end condition to explicitly terminate on all non-numerics.
Second, BP will not read a Text file past an EOF character at all, regardless of its location in the file. The fix for this is inelegant (inline buffer check), but I can move this out to an external proc if it's onerous to maintain.
It's likely there are things I haven't thought of, so I appreciate comments on it.
Sterling Post your free ad now! Yahoo! Canada PersonalsIndex: text.inc
===
RCS file: /FPC/CVS/fpc/rtl/inc/text.inc,v
retrieving revision 1.29
diff -w -b -i -u -p -1 -0 -r1.29 text.inc
--- text.inc14 Feb 2005 17:13:29 - 1.29
+++ text.inc26 Mar 2005 21:34:02 -
@@ -756,21 +756,21 @@ Begin
End;
{$endif HASWIDECHAR}
{*
Read(Ln)
*}
Function NextChar(var f:Text;var s:string):Boolean;
begin
- if TextRec(f).BufPosTextRec(f).BufEnd then
+ if (TextRec(f).BufPosTextRec(f).BufEnd) {$ifdef EOF_CTRLZ} and
(TextRec(f).Bufptr^[TextRec(f).BufPos]#26) {$endif} then
begin
if length(s)high(s) then
begin
inc(s[0]);
s[length(s)]:=TextRec(f).BufPtr^[TextRec(f).BufPos];
end;
Inc(TextRec(f).BufPos);
If TextRec(f).BufPos=TextRec(f).BufEnd Then
FileFunc(TextRec(f).InOutFunc)(TextRec(f));
NextChar:=true;
@@ -784,43 +784,43 @@ Function IgnoreSpaces(var f:Text):Boolea
{
Removes all leading spaces,tab,eols from the input buffer, returns true if
the buffer is empty
}
var
s : string;
begin
s:='';
IgnoreSpaces:=false;
{ Return false when already at EOF }
- if (TextRec(f).BufPos=TextRec(f).BufEnd) then
+ if (TextRec(f).BufPos=TextRec(f).BufEnd) {$ifdef EOF_CTRLZ} and
(TextRec(f).Bufptr^[TextRec(f).BufPos]=#26) {$endif} then
exit;
while (TextRec(f).Bufptr^[TextRec(f).BufPos] in [#9,#10,#13,' ']) do
begin
if not NextChar(f,s) then
exit;
{ EOF? }
- if (TextRec(f).BufPos=TextRec(f).BufEnd) then
+ if (TextRec(f).BufPos=TextRec(f).BufEnd) {$ifdef EOF_CTRLZ} or
(TextRec(f).Bufptr^[TextRec(f).BufPos]=#26) {$endif} then
break;
end;
IgnoreSpaces:=true;
end;
procedure ReadNumeric(var f:Text;var s:string);
{
Read numeric input, if buffer is empty then return True
}
begin
repeat
if not NextChar(f,s) then
exit;
- until (length(s)=high(s)) or (TextRec(f).BufPtr^[TextRec(f).BufPos] in
[#9,#10,#13,' ']);
+ until (length(s)=high(s)) or not (TextRec(f).BufPtr^[TextRec(f).BufPos] in
['+','-','.',',','0'..'9']);
end;
Procedure fpc_Read_End(var f:Text);[Public,Alias:'FPC_READ_END']; iocheck;
{$ifdef hascompilerproc} compilerproc; {$endif}
begin
if TextRec(f).FlushFuncnil then
FileFunc(TextRec(f).FlushFunc)(TextRec(f));
end;
@@ -1049,24 +1049,25 @@ Begin
end;
exit;
end;
If TextRec(f).BufPos=TextRec(f).BufEnd Then
FileFunc(TextRec(f).InOutFunc)(TextRec(f));
hs:='';
if IgnoreSpaces(f) then
begin
{ When spaces were found and we are now at EOF,
then we return 0 }
- if (TextRec(f).BufPos=TextRec(f).BufEnd) then
+ if (TextRec(f).BufPos=TextRec(f).BufEnd) {$ifdef EOF_CTRLZ} or
(TextRec(f).Bufptr^[TextRec(f).BufPos]=#26) {$endif} then
exit;
ReadNumeric(f,hs);
end;
+ if (hs '') then
{$ifdef hascompilerproc}
Val(hs,l,code);
{$else hascompilerproc}
Val(hs,fpc_Read_Text_SInt,code);
{$endif hascompilerproc}
If code0 Then
InOutRes:=106;
End;
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
[fpc-devel] Quick patch for bug 3762
Turns out the CRT unit in OS/2-- which, by my searches, uses #13#10 as CRLF -- was recognizing #13 alone as CRLF. #10 was completed ignored. SterlingPost your free ad now! Yahoo! Canada PersonalsIndex: crt.pas === RCS file: /FPC/CVS/fpc/rtl/os2/crt.pas,v retrieving revision 1.8 diff -w -b -i -u -p -1 -0 -r1.8 crt.pas --- crt.pas 14 Feb 2005 17:13:31 - 1.8 +++ crt.pas 27 Mar 2005 04:27:58 - @@ -379,25 +379,22 @@ var ca:Pchar; begin i:=0; getcursor(y,x); while i=len-1 do begin case s[i] of #8: x:=x-1; #9: x:=(x-lo(windmin)) and $fff8+8+lo(windmin); - #10: ; - #13: begin - x:=lo(windmin); - inc(y); -end; + #10: inc(y); + #13: x:=lo(windmin); else begin ca:[EMAIL PROTECTED]; n:=1; while not(s[i+1] in [#8,#9,#10,#13]) and (x+n=lo(windmax)) and (ilen-1) do begin inc(n); inc(i); end; ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
[fpc-devel] Patch for bug 2453
This is my first shot, so be gentle :-)
The patch assumes FP wants sufficient compatibility with BP 7. If so, it
fixes two problems; if not, at least it was a fun exercise.
First, BP ignores non-numeric characters when a ReadLn is called with an
integer parameter. To fix this, I changed ReadNumeric's end condition to
explicitly terminate on all non-numerics.
Second, BP will not read a Text file past an EOF character at all,
regardless of its location in the file. The fix for this is inelegant
(inline buffer check), but I can move this out to an external proc if it's
onerous to maintain.
It's likely there are things I haven't thought of, so I appreciate comments
on it.
Sterling
Index: text.inc
===
RCS file: /FPC/CVS/fpc/rtl/inc/text.inc,v
retrieving revision 1.29
diff -w -b -i -u -p -1 -0 -r1.29 text.inc
--- text.inc14 Feb 2005 17:13:29 - 1.29
+++ text.inc26 Mar 2005 21:34:02 -
@@ -756,21 +756,21 @@ Begin
End;
{$endif HASWIDECHAR}
{*
Read(Ln)
*}
Function NextChar(var f:Text;var s:string):Boolean;
begin
- if TextRec(f).BufPosTextRec(f).BufEnd then
+ if (TextRec(f).BufPosTextRec(f).BufEnd) {$ifdef EOF_CTRLZ} and
(TextRec(f).Bufptr^[TextRec(f).BufPos]#26) {$endif} then
begin
if length(s)high(s) then
begin
inc(s[0]);
s[length(s)]:=TextRec(f).BufPtr^[TextRec(f).BufPos];
end;
Inc(TextRec(f).BufPos);
If TextRec(f).BufPos=TextRec(f).BufEnd Then
FileFunc(TextRec(f).InOutFunc)(TextRec(f));
NextChar:=true;
@@ -784,43 +784,43 @@ Function IgnoreSpaces(var f:Text):Boolea
{
Removes all leading spaces,tab,eols from the input buffer, returns true if
the buffer is empty
}
var
s : string;
begin
s:='';
IgnoreSpaces:=false;
{ Return false when already at EOF }
- if (TextRec(f).BufPos=TextRec(f).BufEnd) then
+ if (TextRec(f).BufPos=TextRec(f).BufEnd) {$ifdef EOF_CTRLZ} and
(TextRec(f).Bufptr^[TextRec(f).BufPos]=#26) {$endif} then
exit;
while (TextRec(f).Bufptr^[TextRec(f).BufPos] in [#9,#10,#13,' ']) do
begin
if not NextChar(f,s) then
exit;
{ EOF? }
- if (TextRec(f).BufPos=TextRec(f).BufEnd) then
+ if (TextRec(f).BufPos=TextRec(f).BufEnd) {$ifdef EOF_CTRLZ} or
(TextRec(f).Bufptr^[TextRec(f).BufPos]=#26) {$endif} then
break;
end;
IgnoreSpaces:=true;
end;
procedure ReadNumeric(var f:Text;var s:string);
{
Read numeric input, if buffer is empty then return True
}
begin
repeat
if not NextChar(f,s) then
exit;
- until (length(s)=high(s)) or (TextRec(f).BufPtr^[TextRec(f).BufPos] in
[#9,#10,#13,' ']);
+ until (length(s)=high(s)) or not (TextRec(f).BufPtr^[TextRec(f).BufPos] in
['+','-','.',',','0'..'9']);
end;
Procedure fpc_Read_End(var f:Text);[Public,Alias:'FPC_READ_END']; iocheck;
{$ifdef hascompilerproc} compilerproc; {$endif}
begin
if TextRec(f).FlushFuncnil then
FileFunc(TextRec(f).FlushFunc)(TextRec(f));
end;
@@ -1049,24 +1049,25 @@ Begin
end;
exit;
end;
If TextRec(f).BufPos=TextRec(f).BufEnd Then
FileFunc(TextRec(f).InOutFunc)(TextRec(f));
hs:='';
if IgnoreSpaces(f) then
begin
{ When spaces were found and we are now at EOF,
then we return 0 }
- if (TextRec(f).BufPos=TextRec(f).BufEnd) then
+ if (TextRec(f).BufPos=TextRec(f).BufEnd) {$ifdef EOF_CTRLZ} or
(TextRec(f).Bufptr^[TextRec(f).BufPos]=#26) {$endif} then
exit;
ReadNumeric(f,hs);
end;
+ if (hs '') then
{$ifdef hascompilerproc}
Val(hs,l,code);
{$else hascompilerproc}
Val(hs,fpc_Read_Text_SInt,code);
{$endif hascompilerproc}
If code0 Then
InOutRes:=106;
End;
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
[fpc-devel] Patch for bug 3774
This patch adds recognition for hex to Val().
SterlingPost your free ad now! Yahoo! Canada PersonalsIndex: sstrings.inc
===
RCS file: /FPC/CVS/fpc/rtl/inc/sstrings.inc,v
retrieving revision 1.35
diff -w -b -i -u -p -1 -0 -r1.35 sstrings.inc
--- sstrings.inc20 Mar 2005 12:45:19 - 1.35
+++ sstrings.inc27 Mar 2005 05:12:42 -
@@ -552,20 +552,25 @@ begin
'%' : begin
base:=2;
inc(code);
end;
'' : begin
Base:=8;
repeat
inc(code);
until (code=length(s)) or (s[code]'0');
end;
+ '0' : if (code length(s)) and (s[code+1]='x') then
+begin
+ base := 16;
+ Inc(code, 2);
+end;
end;
end;
InitVal:=code;
end;
Function fpc_Val_SInt_ShortStr(DestSize: SizeInt; Const S: ShortString; var
Code: ValSInt): ValSInt; [public, alias:'FPC_VAL_SINT_SHORTSTR']; {$ifdef
hascompilerproc} compilerproc; {$endif}
var
u, temp, prev, maxPrevValue, maxNewValue: ValUInt;
base : byte;
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
RE: [fpc-devel] Quick patch for bug 3762
In response to Tomas Hajny:
I'd certainly be willing to give it a try. Granted, I only have Windows XP, but if I'm careful it should be a smooth transition. No promises on a timeline :)
Another problem with Windows (not sure about other OSs) is in bug 2084. (Use the second example in the description.) I was able to narrow down what the problem is, and it's pretty daunting. Essentially, initmouse will call SetMouseEventHandler() in winevent.pp. This spawns a thread that runs EventHandleThread in a fairly tight loop, which captures all console input.
The problem comes when ReadKey then calls KeyPressed, which also attempts to read console input. No matter what, EventHandleThread will capture the input (since it places a call to WaitForSingleObject, waking up the instant something is in the queue), leaving KeyPressed with nothing to process.
My initial attempt to get around this is to tie KeyPressed to EventHandleThread as well. (If you can't beat 'em, join 'em, right?) I've attached the work I've done so far, but it's not quite right. With two ReadKey calls in a row, the first will read the key, the second will exit without even reading the queue. I think this is because the first ReadKey hasn't had a chance to clear the ScanCode variable before the second ReadKey call to KeyPressed (which exits when ScanCode #0). This results in the DOS window outputting a garbage character when the program finishes because there's still something in the queue.
It's possible to fix it by wrapping the contents of ReadKey in a critical section, but that, to me, is just more overhead. I think there's a more elegant solution waiting to be discovered :-)
Thanks,
Sterling
Your message below:
--
Unfortunately, the problem is wider - there are several other issues with the current OS/2 implementation (if you just quickly compare it with e.g. the GO32v2 implementation, you'd find some other problems too - e.g. handling of #8 is surely incorrect etc.).
The main problem is that there's a lot platform independent functionality in Crt unit which is re-implemented for every platform again and again. The best solution would be to throw all the individual implementations away completely and implement cross-platform Crt unit based on capabilities provided by units Keyboard and Video (possibly missing functionalities within these units necessary for Crt could be either handled by platform specific include file, or by extending current Keyboard and/or Video). This issue has been discussed several times in the core team already, but nobody found the time for doing it yet due to higher priority tasks. Would you be willing to give it a try by any chance?Post your free ad now! Yahoo! Canada Personals===
RCS file: /FPC/CVS/fpc/rtl/win32/crt.pp,v
retrieving revision 1.24
diff -w -b -i -u -p -1 -0 -r1.24 crt.pp
--- crt.pp 14 Feb 2005 17:13:32 - 1.24
+++ crt.pp 31 Mar 2005 06:08:59 -
@@ -20,21 +20,22 @@ interface
{$i crth.inc}
procedure Window32(X1,Y1,X2,Y2: DWord);
procedure GotoXY32(X,Y: DWord);
function WhereX32: DWord;
function WhereY32: DWord;
implementation
uses
- windows;
+ windows,
+ winevent;
var
SaveCursorSize: Longint;
{
definition of textrec is in textrec.inc
}
{$i textrec.inc}
@@ -347,130 +348,138 @@ begin
end
else
case Scancode of
// Function keys
$57..$58: inc(Scancode, $2E); // F11 and F12
end;
RemapScanCode := ScanCode;
end;
+var
+ KeyEvt: THandle; // signal that a key is ready for processing
+ KeyPrcEvt: THandle; // signal that the key has been processed
+ KeyBuf: PInputRecord; // pointer to incoming INPUT_RECORD
+ KeyCS: TCriticalSection; // restricts KeyPressed access to single thread
+
+
+procedure OnKeyEvent(var ir: INPUT_RECORD);
+begin
+ KeyBuf := @ir;
+ Windows.SetEvent(KeyEvt);
+ WaitForSingleObject(KeyPrcEvt, INFINITE);
+ Windows.ResetEvent(KeyEvt);
+end;
+
+
function KeyPressed : boolean;
var
nevents,nread : dword;
- buf : TINPUTRECORD;
AltKey: Boolean;
c : longint;
begin
KeyPressed := FALSE;
+ { Leave KeyPrcEvt set at the end of the proc; this avoids deadlocks in }
+ { OnKeyEvent while waiting for the event to signal. }
+ Windows.ResetEvent(KeyPrcEvt);
+
if ScanCode #0 then
KeyPressed := TRUE
else
begin
- GetNumberOfConsoleInputEvents(TextRec(input).Handle,nevents);
- while nevents0 do
- begin
- ReadConsoleInputA(TextRec(input).Handle,buf,1,nread);
- if buf.EventType = KEY_EVENT then
-if buf.Event.KeyEvent.bKeyDown then
+ WaitForSingleObject(KeyEvt, INFINITE);
+
+ if KeyBuf^.Event.KeyEvent.bKeyDown then
begin
{ Alt key is VK_MENU }
{ Capslock key is VK_CAPITAL }
- AltKey := ((Buf.Event.KeyEvent.dwControlKeyState AND
+ AltKey :=
