Gpc July 2005

gpc@gnu.de

25 participants
67 discussions

Packing strings ()
by Contestcen＠aol.com 14 Jul '05

14 Jul '05

> This assumes that you know precisely what the compiler is doing with > your macros, and that compiler optimisations do not achieve better > results than what you have hand-coded. This may be true for executable code generated by the Pascal Macro Compiler, but it is not true for the data declarations that are generated for the packed strings. There is no executable code involved, so the compiler has nothing to optimize. There is no wasted space, so there is nothing that can be improved. Frank Rubin

3 2

Packing strings ()
by Contestcen＠aol.com 14 Jul '05

14 Jul '05

> A perfect hash table allows for constant search time. > > At runtime, you cannot generally generate a perfect hash table > (without overhead that is often not worth it), so O(log N) is > usually ok. > > But you're explicitly talking about compile-time constant strings, > and in this case, you can usually make a perfact hash table. So > that's your comparison. > > As I wrote in PM, have you looked at programs such as gperf? > > These are some of the interesting issues when dealing with a lot of > compile-time constant strings, rather than squeezing out a byte or > two in return for worse performance and unstable programs. Making a perfect hash requires 7 additional tables, 3 independent hashes of the string, 3 tables to convert the hash values into summands, and one table to convert the sums into pointers to the strings. (There is a trick that can reduce this to 5 tables, but it makes the first hashing round slower.) On the other hand, organizing the indices into a heap, as I suggested, requires no extra storage. As I pointed out in earlier posts, the issue of whether to use a hash, or a tree, or even a hash tree is independent of how the strings are stored. It just happens that my method of storing the strings allows you to create a heap that speeds up searching without using any additional storage. Frank Rubin

2 1

Packing strings ()
by Contestcen＠aol.com 14 Jul '05

14 Jul '05

>>> OTOH, strings must be aligned at least to `Integer' size. (Accessing >>> the Capacity and Length fields requires alignment on some platforms >>> and is at least more efficient on others; accessing the characters >>> can also be more efficient when aligned.) Does your preprocessor >>> take care of this? >>> >> Whether you choose to align the length field on an integer-size boundary or >> not is a decision you could make based on a time versus space trade-off. > > Unless you don't want to crash your program on some platforms ... If alignment is required on a particular platform, then there is no decision to make. You have to align the strings. >> The >> macros that I have written happen to store the strings with no gaps at all, and >> do not do any alignment. > >So they're not suitable for portable programs. The prologue of these macros says, "This version is intended mainly as a demonstration." It is an example designed to illustrate some of the features and capabilities of the Pascal Macro Compiler. Users who do not need alignment can use the macros as provided. Users who need alignment can easily add that feature to the macros. If there are any requests from bona fide users of the Pascal Macro Compiler for an alignment feature, then I will be glad to add it. Frank Rubin

1 0

gpc crash
by Peter N Lewis 14 Jul '05

14 Jul '05

gpc crashes compiling the following (erroneous) program. It correctly detects the syntax error, and then crashes with the crash report following. Enjoy, Peter. program peterW; function Doit( Integer(info): Integer ): Integer; begin end; begin end. Date/Time: 2005-07-06 16:57:46.808 +0800 OS Version: 10.4.1 (Build 8B15) Report Version: 3 Command: gpc1 Path: /Developer/Pascal/gpc-20050331/libexec/gcc/powerpc-apple-darwin8.1.0/3.4.3/gpc1 Parent: gpc [19291] Version: ??? (???) PID: 19293 Thread: 0 Exception: EXC_BAD_ACCESS (0x0001) Codes: KERN_PROTECTION_FAILURE (0x0002) at 0x00000004 Thread 0 Crashed: 0 gpc1 0x00003580 locations + 288 (parse.y:2364) 1 gpc1 0x00011a1c main_yyparse + 3648 (parse.c:8495) 2 gpc1 0x000c17c8 toplev_main + 1976 (toplev.c:1826) 3 gpc1 0x00002298 _start + 344 (crt.c:272) 4 gpc1 0x0000213c start + 60 Thread 0 crashed with PPC Thread State: srr0: 0x00003580 srr1: 0x0000f930 vrsave: 0x00000000 cr: 0x22000282 xer: 0x00000000 lr: 0x00003578 ctr: 0x00000001 r0: 0x00003578 r1: 0xbfffe6a0 r2: 0x00000000 r3: 0x42000000 r4: 0x40e011e0 r5: 0x00000002 r6: 0x40e027c8 r7: 0x0000011e r8: 0x00000001 r9: 0x000ebe54 r10: 0x00000023 r11: 0x40f02004 r12: 0x900060ac r13: 0x0033ad0c r14: 0x003455d8 r15: 0x00000001 r16: 0x0044bca8 r17: 0x0033a2fc r18: 0x00300be4 r19: 0x000001f2 r20: 0x00300be4 r21: 0x404cc268 r22: 0x0044346c r23: 0x404cc268 r24: 0xbfffe758 r25: 0x0044346c r26: 0x00000002 r27: 0x00000030 r28: 0x00000001 r29: 0xbfffe788 r30: 0x404cc268 r31: 0x0000346c Binary Images Description: 0x1000 - 0x443fff gpc1 /Developer/Pascal/gpc-20050331/libexec/gcc/powerpc-apple-darwin8.1.0/3.4.3/gpc1 0x40b54000 - 0x40b5bfff libintl.3.dylib /usr/local/lib/libintl.3.dylib 0x8fe00000 - 0x8fe50fff dyld 43 /usr/lib/dyld 0x90000000 - 0x901a6fff libSystem.B.dylib /usr/lib/libSystem.B.dylib 0x901fe000 - 0x90202fff libmathCommon.A.dylib /usr/lib/system/libmathCommon.A.dylib 0x90727000 - 0x90800fff com.apple.CoreFoundation 6.4.1 (368.1) /System/Library/Frameworks/CoreFoundation.framework/Versions/A/CoreFoundation 0x9084b000 - 0x9094dfff libicucore.A.dylib /usr/lib/libicucore.A.dylib 0x909a7000 - 0x90a2bfff libobjc.A.dylib /usr/lib/libobjc.A.dylib 0x90ae3000 - 0x90af5fff libauto.dylib /usr/lib/libauto.dylib 0x91d33000 - 0x91d53fff libmx.A.dylib /usr/lib/libmx.A.dylib 0x92c9b000 - 0x92d89fff libiconv.2.dylib /usr/lib/libiconv.2.dylib 0x93614000 - 0x9361cfff libgcc_s.1.dylib /usr/lib/libgcc_s.1.dylib Model: PowerMac7,3, BootROM 5.1.8f7, 2 processors, PowerPC G5 (3.0), 2 GHz, 1.5 GB Graphics: GeForce FX 5200, GeForce FX 5200, AGP, 64 MB Memory Module: DIMM0/J11, 256 MB, DDR SDRAM, PC3200U-30330 Memory Module: DIMM1/J12, 256 MB, DDR SDRAM, PC3200U-30330 Memory Module: DIMM2/J13, 512 MB, DDR SDRAM, PC3200U-30330 Memory Module: DIMM3/J14, 512 MB, DDR SDRAM, PC3200U-30330 Modem: Jump, , V.92, Version 1.0, Network Service: Built-in Ethernet, Ethernet, en0 Serial ATA Device: ST3160023AS, 149.05 GB Parallel ATA Device: HL-DT-ST DVD-RW GWA-4082B, USB Device: CanoScan, Canon, Up to 12 Mb/sec, 500 mA USB Device: Hub, , Up to 12 Mb/sec, 500 mA USB Device: CF076, CF076, Up to 12 Mb/sec, 500 mA USB Device: Hub in Apple Pro Keyboard, Chicony, Up to 12 Mb/sec, 500 mA USB Device: Apple Optical USB Mouse, Logitech, Up to 1.5 Mb/sec, 100 mA USB Device: Apple Pro Keyboard, Chicony, Up to 12 Mb/sec, 250 mA USB Device: Studio Display, , Up to 1.5 Mb/sec, 500 mA -- <http://www.stairways.com/> <http://download.stairways.com/>

2 2

Packing strings ()
by Contestcen＠aol.com 13 Jul '05

13 Jul '05

>> I don't know the internals of the GPC New procedure, but in various >> environments where I have worked in the past there was no guarantee that successive >> calls to New would allocate adjacent blocks of storage, hence no guarantee that >> there would be no gaps or wasted space. It all depended on what sequence of >> calls to New and Dispose had occurred earlier. > > You can never rely on successive `New' calls to return adjacent > blocks of storage. That's not a reliable way to enlarge an array. > And I don't know of any compiler for Pascal, or any other language > for that matter, where such a thing would work. Sometimes there are > special routines for that (in GPC the non-standard ReAllocMem, use > with caution), otherwise you have to allocate a new array and copy > the existing elements, or use another data structure that doesn't > require contiguous memory, such as lists or trees. I think we have lost the trail here. Peter's original posting on this subject asked if there was a way to store character strings of different lengths without wasting space for the short strings. Frank Heckenbach suggested that Peter store each string using the New procedure, so each string would get a space its own size. I said that the Pascal Macro Compiler could store the strings without any gaps or wasted space. However, this works only if the strings are known at compile time. I also pointed out that using New does not assure that there would be no gaps because New does not always allocate consecutive adjacent blocks of storage. In the storage-allocation system that I use most often, storage is allocated in units of 16 bytes, because free storage is kept in a tree structure with each element containing a length, an up pointer and two down pointers. So if you allocated a separate block for each character string there could be a lot of wasted space. Conclusion: If the strings are known at compile time, the most efficient way to store them without gaps is to use the Pascal Macro Compiler. If the strings are not known until run time, the most efficient way is to allocate a large block of storage, and move the strings in end-to-end, using a separate array to hold either pointers or indices into the large block. When the block is full, allocate another large block using New. There are two ways to manage the storage. (1) Extension block method: Use a second array to point to the set of large blocks. Each string will be accessed using two pointers or two indices. The first will point to the particular block, and the second will point to the string within the block. (2) Single block method: Make the new block twice as large as the previous block, move the existing strings into the new block and then Dispose the old block. Frank Rubin

4 7

Packing strings ()
by Contestcen＠aol.com 13 Jul '05

13 Jul '05

>> If the strings are not known until run time, the most >> efficient way is to allocate a large block of storage, and move the >> strings in end-to-end, using a separate array to hold either pointers or >> indices into the large block. >> >> When the block is full, allocate another large block using New. There >> are two ways to manage the storage. (1) Extension block method: Use a >> second array to point to the set of large blocks. Each string will be >> accessed using two pointers or two indices. The first will point to the >> particular block, and the second will point to the string within the >> block. (2) Single block method: Make the new block twice as large as >> the previous block, move the existing strings into the new block and >> then Dispose the old block. > >Very convoluted. A linked list or string collection would do just fine. >And I am still not sure how you can make the claim that one method or >the other is the "most efficient" way of doing something. In this case I should have said "the most efficient ways that I know." A linked list of strings may or may not be comparably efficient in terms of space usage. In the extension block method, for each block of strings you also need a table of integer indices into the block. The pointers in the linked list are probably twice as large as the integer indices, so they take more room. In addition, the pointers may need to be aligned, so they may take an average of 5.5 bytes, compared to 2 bytes for the indices. On the other hand, you don't know beforehand how many strings you will have, so you might allocate the index table larger than is actually needed. However, the index table offers an advantage. It can be sorted according to the alphabetic order of the strings, so the table can be searched by a binary search, or they may be arranged into a heap, which also makes for log(N) time searching. Both of these methods require no extra storage. On the other hand, the linked list has to be searched serially. If you chose to use a hash table with the linked list, that would occupy even more storage. As I indicated in an earlier posting, the decision to use a hash table, heap or tree to speed up access to the strings is independent of the method used to store the strings. To head off any future argument that doubling the size of the single block can waste a lot of storage, let me point out that doubling is just an example. You could increase it by half, or by 10% each time, at the expense of copying the list of strings more frequently. This is simply a time-vs-space trade-off. Frank Rubin

2 1

Packing strings ()
by Contestcen＠aol.com 13 Jul '05

13 Jul '05

> OTOH, strings must be aligned at least to `Integer' size. (Accessing > the Capacity and Length fields requires alignment on some platforms > and is at least more efficient on others; accessing the characters > can also be more efficient when aligned.) Does your preprocessor > take care of this? > Whether you choose to align the length field on an integer-size boundary or not is a decision you could make based on a time versus space trade-off. The macros that I have written happen to store the strings with no gaps at all, and do not do any alignment. If you decided that for your application and platform aligning the strings was better, then you would not use my macros, you would write your own macros, or modify my macros to align the strings. The Pascal Macro Compiler is a general-purpose preprocessor, and can align or not align as the user wishes. > >> Conclusion: If the strings are known at compile time, the most efficient way >> to store them without gaps is to use the Pascal Macro Compiler. If the >> strings are not known until run time, the most efficient way is to allocate a large >> block of storage, and move the strings in end-to-end, using a separate array >> to hold either pointers or indices into the large block. > > Not necessarily. There are various data structures such as hashes, > lists and trees for a reaons. Each have their particular advantages > and disadvantages. Which one is best, depends on the application and > is not always easy to decide. Claiming that any particular method is > "the most efficient" without qualification doesn't give your > statements much credibility, sorry. > How you store the strings and how you access the strings are completely separate issues. You can decide to use hash tables, threaded lists, heaps, or trees for accessing the strings regardless of whether you store the strings in a fixed-width table of strings, end-to-end in a character array, or each in a separately allocated block of storage. These decisions can be made independently. I am dealing here solely with the issue of how to store the strings with the least possible amount of wasted space. > > At least you got the quoting right this time. :-) > There is no "right" way to do quoting. Different people have different preferences. I simply followed the style that is used in this particular forum. Frank Rubin

2 1

Packing strings ()
by Contestcen＠aol.com 13 Jul '05

13 Jul '05

>> Conclusion: If the strings are known at compile time, the most >> efficient way to store them without gaps is to use the Pascal Macro >> Compiler. > > A very bold claim indeed - and I am not sure how you can make such a > claim, without seeing every string-handling routine that every > programmer has written. > Using the Pascal Macro Compiler you can store the strings with no gaps and no wasted space whatsoever. I don't see how you can improve on that. Moreover, the method requires no code, makes no calls, and takes no time at run time. I don't see how you can improve on that. Frank Rubin

2 1

range checking
by Peter N Lewis 10 Jul '05

10 Jul '05

Ok, I've got my application compiling and linking (all 250+ units). Now I'm trying to test it out. Currently it is crashing out with range checks. The first was one I'm used to with GPC, passing an SInt32 to a UInt32 (often these types are used interchangeably by the system to refer to a generic block of four bytes (eg random number seed) and so ensuring they match is not normally that important, but GPC range checks on these. I've written SafeCast functions for Signed to Unsigned and vice versa. I guess I'll eventually catch them all. The next one is more challenging, since I don't see a good workaround. s: String(255) @s[1] range checks if Length(s) is 0. While this might technically be correct (the subscript is out of bounds), the actual address is valid. This is quite challenging to work around, since I'm often forced to deal with strings as a pointer to chars and a length, and this means that code to say draw a string like: DrawString( @s[1], Length(s) ); now needs to special case for s = ''. I would contend that in the case of @s[x], x should be checked against a range of 1..Length(x)+1 because it should be legal to point to the next free character. Whether this is reasonably doable or not, I don't know. If s were short strings, I could work around it with pointer arithmetic (@s+1), but given it is a Schema, I don't know how I would safely get the address of the first character of the string in the case where s might be empty. More precise control over range checking ,might be helpful, options to disable range checking for strings, or perhaps limit them to capacity range checking, as well as disabling range checking on casts would be nice to get things going (I prefer to run with as much protection as possible generally, but sometimes range checking can be overly enthusiastic). Peter. -- <http://www.stairways.com/> <http://download.stairways.com/>

3 2

range checking code generation error
by Peter N Lewis 10 Jul '05

10 Jul '05

The following code works correctly if --no-range-checking, but fails with range checking enabled (as it is by default). % gp --no-range-checking peterY.pas % ./peterY OK % gp peterY.pas % ./peterY failed Looking at the assembly, it seems erroneously pass a local variable address (temporary?) to the var parameter. Thanks, Peter. program peterX; type SInt32 = Integer attribute( size = 32 ); UInt32 = Cardinal attribute( size = 32 ); procedure Doit( var x: SInt32 ); begin x := 5; end; var y: UInt32; begin y := 1; Doit( SInt32(y) ); if y = 5 then begin WriteLn( 'OK' ); end else begin WriteLn( 'failed' ); end; end. -- <http://www.stairways.com/> <http://download.stairways.com/>

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

1995

Gpc July 2005