Tag Archives: programming

Why Garbage Collectors Should Avoid the Use of Reference Counts

I made a comment in one my posts some time ago that I thought SPITBOL was superior to Python in that it contains a compacting mark-sweep garbage collector with recognition of sediments.

Python uses reference counts to detect unreachable memory. SPITBOL was written in the 1960’s, so the use of compacting garbage collectors was a well known technology when Python was created in the 1980’s.

For example, I one wrote a small Python program that ran in quadratic time due to the use of reference counts.

A user commented that they thought this was a snide remark, and that the use of reference counts was perfectly fine.

I just downloaded Remarkable, a markdown editor and viewer, written in Python.

I just used it to process a markdown format file, and got the following error message:

 

java version "1.7.0_121"
OpenJDK Runtime Environment (IcedTea 2.6.8) (7u121-2.6.8-1ubuntu0.14.04.3)
OpenJDK 64-Bit Server VM (build 24.121-b00, mixed mode)
/usr/lib/python3/dist-packages/remarkable/__init__.py:53:
 Warning: g_object_ref: assertion 'object->ref_count > 0' failed
  Gtk.main()
/usr/lib/python3/dist-packages/remarkable/__init__.py:53:
 Warning: g_object_unref: assertion 'object->ref_count > 0' failed
  Gtk.main()
*Spellchecking not enabled.
*To enable spellchecking install pygtkspellcheck
*https://pypi.python.org/pypi/pygtkspellcheck/

 

 

 

As a young child one of my favorite comic strips was Snuffy Smith.

 

Snuffy often ended a conversation by saying, “‘Nuff Said.'”

Well, this is for the snide commenter:

‘NUFF SAID.

 

 

 

I

 

 

Advertisements

On being the maintainer, sole developer, and probably the sole active user of the programming language SPITBOL

As best as I can tell, I am in what I believe to be a unique situation:

I am the maintainer, sole developer, and probably the only active user of the programming language SPITBOL.

(If you know of anyone else who is maintaining an open-source implemenation of a programming language that has only one user, please let me know, via comments to this post.)

Let me explain.

In June of this year I took over maintainership of Macro SPITBOL. Mark Emmer had labored for almost a quarter century in this task. He kept Macro SPITBOL alive, and that is the task I face going forward.

Macro SPITBOL, the work of Robert B. K. Dewar and the late A. P. “Tony” McCann, is the best implementation of the SNOBOL4 language yet created. I believe it to be a remarkable accomplishment.

SNOBOL was created at Bell Labs in the early 60’s. The basic reference is The SNOBOL4 Programming Language, by R. E. “Ralph” Griswold, J. F. Pogue, and and I. P. Polonsky. It is known to SNOBOL4/SPITBOL folks as just “The Green Book,” due to the color of its cover. (Mark Emmer secured the rights to make it available, and the pdf for the book is freely above at the cited URL.)

SNOBOL was the first language to address processing strings and text in a serious way. It’s most notable innovation was the notion of “pattern.” As part of this, it introduced many primitives such as BREAK and SPAN. Those terms are now commonly used in many libraries and programs that process text.

SNOBOL was one of several languages widely taught in “Introduction To Programming” courses in the 70’s and early 80’s.Then — I think it fair to say — SNOBOL sank into obscurity.

Macro SPITBOL was created in the mid 70’s. Dewar and McCann finished their work by the late 70’s. I did the port to CDC 6600 in the late 70’s, and worked with Robert to do the port to the IBM/PC 8086 in 1983. Mark Emmer then took over the project, and did ports to Mac, Solaris, and various versions of Unix.

At most ten people worked on refining the SPITBOL implementation. I’m the only one still working on it. Mark lends a hand now and then, but more as an advisor than programmer.

Since taking over maintainership I have finished the Linux port (Mark had already done most of the heavy lifting). I started writing about SPITBOL on this b log to drum up interest, and I am actively working on the port to Apple’s OSX, to be followed by a port to the ARM architecture, so that SPITBOL can be made available on Apple’s ioS and Google’s Android operating environments (both use ARM chips).

Here is where the work stands:

  • There have been just over 3,000 downloads of the Windows version since it was released in open-source form in July 2009. I’ve received less than ten, if not zero, emails and blog comments about this version since its release.
  • There have been 30 (thirty) downloads of the Linux version since it was released two months ago. I’ve heard back from few than five people that they have downloaded it and also tried it.
  • While a few (under 10) folks have expressed interest in the work, no one has stepped forward to work on the code as a developer.
  • I’ve seen no sign anyone is actively using SNOBOL4/SPITBOL in a serious way. SPITBOL was once used by folks in the linguistics community, but I’ve seen no sign of recent work.
  • I did a search on Google for “SPITBOL” in June and got about 17,000 matches. I also did a search on “SNOBOL4” and got about 47,000 matches. I just repeated the searches and got the same results.
  • Despite making many posts about SPITBOL on my blog, I have yet to see any one of them achieve more than 20 or so views.

In summary, though I know I have advanced the code, I have been a failure trying to drum up interest in the project.

What Next?

I am not giving up. I have several reasons to push on:

  • SPITBOL is unique in the power it provides to manipulate strings and text. I’ve yet to see anything else come close.
  • SPITBOL is both amazingly fast and compact. It can compile hundreds of thousands of lines of code per second, in a program consisting of under 20,0000 executable instructions. It runs at the hardware level. For example, it includes a compacting mark-sweek garbage collector, while I know of at least one widely-used programmng language that still uses reference counts. [1]
  • The ARM implementation should be *very* fast.
  • I have packaged the system so it is self-hosting. SPITBOL uses tcc for its C compiler, NASM for its assembler, musl libc for its runtime libraries, and Rob Lanbley’s toybox to provide basic Unix commands. SPITBOL is built with these open-source packages, and the source for them is included in the SPITBOL distribution, so you get not only Macro SPITBOL, but a complete development environment to boot.
  • I believe there is a great opportunity due to the poor support for Unicode in other programming languages and libraries. If I can add full support for Unicode, I hope to realize “if you build it, they will come.”
  • Perhaps most important: SPITBOL is fun!. I’ve been programming for over fifty years, and I have never had so much fun save when I was working on SPITBOL, as either user of the language or as an implementer.
  • The quality of the system will speak for itself: Code Talks.
  • Knowing that I am starting from zero, any progress will be great news, and it will be fun to see how far I can get. I had a similar experience working with Philippe Charles on Jikes. We started from nothing, and were able to build something that achieved some success. I hope to repeat that, and I know I will have fun trying to do so, even if I don’t succeed.

It is also evident that talking about SPITBOL is a thankless task for now, so I’m going to put off blogging, twittering and such, so I can concentrate on the coding, which after all is all that matters.

Most importantly, I believe that polishing the implementation and porting it to new environments is not enough.

The *only* way to move the project forward is to finish needed refinement and ports as soon as possible, and then to use the result to write applications in SPITBOL that demonstrate what can done when programming in SPITBOL.

I have a few ideas about useful applications, and hope to get to work on them as soon as possible.

We shall see…

Notes:

1. Can you name a widely-used contemporary programming language that still uses the 60’s software technology of reference counts to manage storage?

Aggressive Assembly Language Programming in SPITBOL

The Preface to “Macro SPITBOL: The High-Performance SNOBOL4 Language,” by Mark B. Emmer and Edward K. Quillen, includes the following:

Robert Dewar created Macro SPITBOL in the mid 1970’s, and showed the world that a high-performance version of SNOBOL4 was possible. His Macro SPITBOL compiler forms the kernel of this implementation. As an example of “aggressive” assembly-language-programming, it remains a programs tour de force.

I was reminded of this when I came upon a comment by Mark in the source for Macro SPITBOL:

note: as an experiment, we tried aligning all ent and prc’s on a dword boundary, in an attempt to minimize instruction stall time on the first opcode of a procedure. the resultant exe file waslarger by 592 bytes, and actually ran 0.1% slower. we will continue to use odd alignment of block entry routines so that the .cepp conditional may be used.

592 bytes? 0.1% difference in performance?

Can you think of another programmer who pays this level of attention to performance?

Here is another:


* move chars from xl (esi) to xr (edi), count in wa (ecx)
*
* the following sequence "old method" is shorter than the "new method"
* shown below, but is much slower because of the conditional jumps that
* cause the instruction cache to be flushed for 3 out of 4 count values.
*
* old method:
* shr ecx,1
* jnc tmp1
* movsb ; move odd byte
* tmp1 shr ecx,1
* jnc tmp2
* movsw ; move odd word
* tmp2 rep movsd ; move string as double words
*
* genop('shr','ecx','1')
* genop('jnc','short ' (t1 = genlab()))
* genop('movsb')
* genopl(t1 label.delim,'shr','ecx','1')
* genop('jnc','short ' (t1 = genlab()))
* genop('movsw')
* genopl(t1 label.delim,'rep','movsd') :(opdone)
*
* new method:
* shrd eax,ecx,1 ; preserve ecx[0] in eax[31]
* shr ecx,2 ; preserve ecx[1] in cy, divide by 4
* rep movsd ; move dwords, leaves ecx=0
* adc ecx,ecx ; copy cy to ecx[0]
* rep movsw ; copy 1 or 0 words, leaves ecx=0
* shld ecx,eax,1 ; copy eax[31] to ecx[0]
* rep movsb ; copy 1 or 0 bytes

elel

Some knowledge — indeed more than I have — of programming for Intel’s x86 architecture is needed to fully appreciate the above, but the attention to detail is obvious.

Dewar’s MACRO SPITBOL was preceded by SPITBOL/360, written in IBM360 Assembly Language in the late 1960’s by Dewar and Ken Belcher. [1]

It must be the most efficient 360 assembly language program ever written. Robert once remarked that it was the only program known to him where the authors kept a copy of the instruction timing/cycle details for each model of the 360 in front of them as they wrote the code, and they frequently consulted these details to decide on best code sequence.

SPITBOL/360 demonstrated an astounding level of performance. SPITBOL/360 routinely compiled hundreds of thousands of lines of source code per second.

I once heard, perhaps from Robert himself, of one of the great tricks in SPITBOL/360.

SNOBOL has an integer variable &STLIMIT. A counter is initially set to this value. Whenever a new statement is executed, the counter is decremented, and if the value reaches zero then an exception is raised. This is used to avoid runaway loops and other code that would result in execution going on forever.

The obvious method is to use an integer counter, decrement it when a new statement is executed, and raise the exception when the value zero is reached.

Dewar and Belcher’s device was to maintain the counter as a floating-point (real) variable. It was set by computing a “magic” value and initializing the counter to that value. When a new statement was executed, the value 1.0 was added to the floating point counter. The magic was in that a floating-point exception, due to overflow of the value, would be raised at the appropriate time.

Andy Koenig — a fellow contributor to Macro SPITBOL — made mention of this device in his column Some Programs Are Poorly Designed On Purpose. The post includes several other examples from SPITBOL of what Andy calls “nefarious purposes” in the use of floating point arithmetic.

Another device, one of much greater generality, was the use of indirect threaded code (ITC), described in Dewar’s paper Indirect Threaded Code.

Most interpreters use a “switch on opcode” statement when a new statement is to be execute. However, this involves testing the value, and doing a switch instruction to the appropriate code, which tends to slow things down. Indeed this is one of the main costs of writing an interpreter instead of generating actual code for the target machine. After all, the hardware is designed to extract opcodes and take the appropriate execution as fast as it is possible.

When using ITC, the transition from one abstract instruction to the next is made not by a switch, but by doing an “indirect branch” to the address contained in the the code block for the next statement.

By the way, this is the reason you cannot write code in C to execute the Minimal assembly language level code in which SPITBOL is written. C has no such contruct (what is needed is something like goto *p).

By the way, Dewar is equally aggressive when it comes to documenting his code. See for example the source code for SPITBOL in file spitbol.min available at Github Hardbol SPITBOL. I consider it a tour de force in program documentation.

For example, while working together on the port of Macro SPITBOL to the IBM PC in the early 80’s, I remember particularly an instance where Dewar saved a file, and then immediately went back to edit the source when he noticed there was an extraneous space..

Notes:

1. SPITBOL/360 is available in open source form under the GPL license. See SPITBOL 360.

Dewar and Belcher applied their aggressive programing techniques in the early 80’s by writing a COBOL compiler in COBOL! The wikipedia entry for Robert Dewar includes:

In the 1970s Dewar was a principal author of the Realia COBOL compiler, widely used in commercial environments to this day (marketed by Computer Associates).

Written in COBOL, a remarkable feat in itself, I learned later from colleagues at IBM that Realia COBOL generated code that was better than that produced by IBM’s product COBOL compiler

  • Pages

  • December 2017
    M T W T F S S
    « Apr    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • RSS The Wayward Word Press

  • Recent Comments

    mrrdev on On being the maintainer, sole…
    daveshields on On being the maintainer, sole…
    James Murray on On being the maintainer, sole…
    russurquhart1 on SPITBOL for OSX is now av…
    dave porter on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated