When I write n (unsigned-byte 4)s to my file-system (solaris 2.6 on a sparc
clone), and then I say ls -l to look at the size of the file, there are n
bytes in the file rather than n/2 as I would have expected. Does this mean
the file system can write nothing smaller than an 8-bit byte? If so, does
this in any way affect what happens when I read an (unsigned-byte 4) from
the same file. I've played with this some, and the values appear to be
correct, but I'm still wondering what's happening 'below the surface'. Is it
still the case that an array of n 4-bit bytes will occupy (roughly) n/2
bytes of main memory when loaded into lisp? (Apologies if this is an
elementary computer science question.)

As far as file I/O goes, all that's guaranteed is that if you write a file
with a particular element type, and then read it back with the same element
type, you'll get the same values.  It would be difficult to specify how the
data is represented in the file in an OS-independent way.  For instance,
how should it write (unsigned-byte 8) elements on a machine with with
36-bit words and 9-bit bytes?  Should it write each 8-bit byte into a 9-bit
file byte or pack them in tightly?  If it packs them, should the 5th byte
be written to the 2nd word or straddle the word boundaries?  Should it be
big-endian or little-endian?

  why did you expect that?

| Does this mean the file system can write nothing smaller than an 8-bit
| byte?

  the file system has nothing to do with it.  Unix doesn't know about file
  contents at all, and as an operating system design, takes significant
  pride in that fact.

| If so, does this in any way affect what happens when I read an
| (unsigned-byte 4) from the same file.

  if you write (unsigned-byte 4) to a file and read it again, you should
  get the exact same values back.  how these bits are stored is none of
  your business.

  if your expectations can be defended and you have reason to use this
  feature to obtain improved storage performance, talk with your CL vendor
  and have them make it work for you.

| I've played with this some, and the values appear to be correct, but I'm
| still wondering what's happening 'below the surface'.

  the only people who can really answer that question is the person who
  implemented the feature in your Common Lisp implementation.  finding that
  person may be hard, but if you use free software, the source is there.
  if not, you should use the customer support facilities of the vendor.

| Is it still the case that an array of n 4-bit bytes will occupy (roughly)
| n/2 bytes of main memory when loaded into lisp?

  if it makes performance sense to do so, or people have argued for this
  feature even if it didn't, it will.  you can, however, easily measure the
  space costs of an allocation.  for instance,

(time (make-array 1000 :element-type '(unsigned-byte 4) :initial-element 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  14 msec
; space allocation:
;  9 cons cells, 0 symbols, 512 other bytes, 0 static bytes
=> #(0 0 0 0 0 0 0 0 0 0 ...)
(4) cl-user
(time (make-array 1000 :element-type '(unsigned-byte 8) :initial-element 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  0 msec
; space allocation:
;  9 cons cells, 0 symbols, 1,016 other bytes, 0 static bytes
=> #(0 0 0 0 0 0 0 0 0 0 ...)
(5) cl-user
(time (make-array 1000 :element-type '(unsigned-byte 2) :initial-element 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  0 msec
; space allocation:
;  9 cons cells, 0 symbols, 512 other bytes, 0 static bytes
=> #(0 0 0 0 0 0 0 0 0 0 ...)
(6) cl-user
(time (make-array 1000 :element-type '(unsigned-byte 1) :initial-element 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  0 msec
; space allocation:
;  9 cons cells, 0 symbols, 144 other bytes, 0 static bytes
=> #*0000000000.. ; [abbreviated by me]
(7) cl-user
(time (make-array 1000 :element-type '(unsigned-byte 16) :initial-element 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc)     0 msec user, 0 msec system
; cpu time (total)  0 msec user, 0 msec system
; real time  0 msec
; space allocation:
;  9 cons cells, 0 symbols, 2,016 other bytes, 0 static bytes
=> #(0 0 0 0 0 0 0 0 0 0 ...)

  the reported results show the storage strategies and optimizations for
  various data types.

Thanks for your response.

Hi Bruce,

If it is a solid requirement that 4 bits' worth of data occupy no more
than 4 bits in the file, and the smallest unit you can write is 8 bits,
then a practical way to do it is to merge 4-bit values into 8-bit values
before writing (and vice versa after reading).  Check out the Numbers
section of the Hyperspec for bit-manipulation like ASL.

If it is not a strict requirement, don't worry about the overhead or use
ZIP :-)

Robert

LDB and DPB are your friends.

i offer you a couple functions i wrote a while back.  please excuse
the short variable names.  i was fighting unix/C brain-damage at the
time.  please feel free to use them as you wish.

;; pack bytes into an integer
(defun pack-word (bl                    ; byte list
                  sl                    ; size list
                  &optional
                  (acc 0)               ; original byte
                  (pos 0))              ; initial position
  (if (and bl sl)
      (pack-word (cdr bl)
                 (cdr sl)
                 (dpb (car bl) (byte (car sl) pos) acc)
                 (+ pos (car sl)))
      (values acc pos)))

;; unpack bytes in integer word word using lengths in the size list
(defun unpack-word (word                ; packed word
                    sl)                 ; size list
  (let ((pos 0)
        (bl nil))
    (dolist (sz sl)
      (push (ldb (byte sz pos) word) bl)
      (incf pos sz))
    (values (nreverse bl) pos)))

examples:

USER(18): (pack-word '(3 9) '(4 4))
147
8
USER(19): (unpack-word 147 '(4 4))
(3 9)
8

hope this helps.

Andrew

I don't want to get into details about the specific problem that
was being discussed, but I do want to respond to this:

========
See http://t2r.uwasa.fi/jargon/byte.html for a fairly thorough discussion
of the term "byte".  It generally follows my own understanding of the term,
as well as the info I was able to search for on the net.  As a former
Sperry/Univac employee, I am knowledgable of bytes being anywhere from
5 to 9 bits, especially on 36-bit machines (the Univac 1100 series
had these different byte sizes).  But I hadn't known about the PDP-10,
whose byte sizes could vary from 1 to 36 bits!  ... It was the
aforementioned variability of the byte on which CL based its term ...

  [ ... ]

IBM (really Werner Buchholz) coined the term byte in 1956.  But until
the 70's or 80's, it was never clear what size you were talking about,
unless you were clear on your context: if you were in IBM culture,
the byte was clearly 8 bits most of the time.  But if you were in the
company of Eniac/Univac or DEC people, then a byte could mean simply
"a character" which also implied many potential sizes.  It is ironic
that we are actually departing from the old tradition of calling a
byte a character, by going to two-byte characters. [ed: but not always
two bytes]

I would guess that whatever committee [a developer] said standardized on
the term "octet" was aware of this issue, and I wouldn't be surprised
if their reasoning for letting go of "byte" wasn't precisely this
reason that it would be too non-definitive.
======

Because of this and further discussion, we have standardized on the
term "octet" when we describe 8-bits specifically.  The proposal that
resulted from this is part of a design of an I/O system, which will
complement the current Gray streams system we currently have, but
which will address various issues of stream mutivalency, multibyte
character sets and locales, speed, and a few other problems that the
CL spec and Gray streams don't currently address.  We hope to publish
this proposal soon, long before our next major release.

Cheers

  how can _proposals_ be proprietary?  sheesh.

  work on this topic was "commissioned" at the last X3J13 meeting, and
  Franz accepted the responsibility to oversee the work if not write it.

  locate your misplaced calm and _breathe_, mister, you're near hysterical.

  if you know that the medium is an 8-bit medium, opening a stream for
  writing to or reading from it as (UNSIGNED-BYTE 8) is guaranteed to
  produce the expected results by virtue of the insanity of not doing so.

  if you need control over the individual bits, you don't request a service
  where you explicitly say "do the smartest thing you can with my request".

  please realize that the Common Lisp community is more than 40 years old.
  collectively, the community has already been where every clueless newbie
  will be going for the next three years.  so relax, please.

byte n. 1. adjacent bits within an _integer_. (The specific number of bits
can vary from point to point in the program; see the _function_ BYTE.)
                     -- from the Common Lisp the Standard (ANSI X3.226-1994)

| If not the OS, then what system determines how an (unsigned-byte 4) or
| any other object gets written to disk?  Does each application make its
| own decisions on this point?

  yes.  Unix doesn't know about file contents.  it stores only bytes (still
  of no predetermined size).  the only common byte size these days is 8,
  but Unix was delivered in the past on machines with 9-bit bytes.  (this
  historical fact has even escaped most C programmers.)

| I just was trying to understand the space considerations of some code I'm
| writing.  I figured there was a direct mapping from the size of the
| internal data structure to the size of the file.

  there never are.

  the first tenet of information representation is that external and
  internal data formats are incommensurate concepts.  there simply is no
  possible way they could be conflated conceptually.  to move from external
  to internal representation, you have to go through a process of _reading_
  the data, and to move from internal to external representation, you have
  to go through a process of _writing_ the data.  these processes are
  non-trivial, programmatically, conceptually, and physically.  that some
  languages make them appear simple is to their credit, but as always,
  programming languages are about _pragmatics_, and it doesn't make sense
  to make conceptually complex things complex to use and program -- quite
  the contrary, in fact.  so the more things that are different look the
  same to a programmer, the higher the likelihood that there is something
  complex and worthwhile going on behind the scenes.

  the second tenet of information representation is that optimizations for
  internal representations are invalid for external representation and vice
  versa.  the crucial difference is that data in internal representation is
  always under the control of the exact same software at all times, while
  data in external representation _never_ is.  therefore, decisions you
  make when optimizing internal representation exploit the fact that you
  have full control over the resources that are being used to represent it,
  such as actually knowing all the assumptions that might be involved,
  while decisions you make when optimizing external representation must
  yield to the fact that you have no control over the resources that are
  being used to represent it.  a corollary is that storing any data in raw,
  memory-like form externally (_including_ network protocols) is so stupid
  and incompetent that programmers who do it without thinking should be
  punished under law and required to prove that they have understood the
  simplest concepts of computer design before they are ever let near a
  computer again.

  the third tenet of information representation is that data in _any_
  external representation is _never_ outlived by the code, and that is an
  inherent quality of external representation: the very reason you decided
  to write it out to begin with is the reason it won't go away when the
  code that wrote it did.  this fact alone so fundamentally alters the
  parameters of optimization of external representation from internal that
  the only consequence of not heeding it is to wantonly destroy information.

  now, there is one particular software company that profits by breaking
  all possible understanding of information representation, and who makes
  their very living from destroying the value of information previously
  committed to the care of their software.  this _started_ through sheer,
  idiotic incompetence on their part, but turned into company policy only a
  few years later: the company mission is now to destroy information like
  no company has ever done before, for the sole purpose of causing the
  customers to continue to pay for software that renders their past useless
  and thus in need of re-creation, data conversion, etc.

| That is, if a thousand-element array of 4-bit bytes takes 512 bytes
| (according to time), and I write the contents of that array to disk, I
| expected to see a 512 byte file.  Not so, apparently.

  avoid the temptation to confuse internal with external representation,
  and you will do fine.  as soon as you think the two are even remotely
  connected (as such -- going through a read/write process is precisely the
  point showing how they are _not_ connected as such), you lose.  big time,
  and the way back to unconfusion is long and hard.  witness all the C
  victims who actually think it makes sense to dump memory to files.  they
  lose so badly you'd think somebody would learn from it, but no -- their
  whole philosophy is to remain braindamaged in the face of danger, as that
  kept them out of the scary, scary task of having to _think_ about things,
  not something C programmers are very good at.

  a 1000-element vector of (unsigned-byte 4) may optimally be stored as 500
  bytes on a disk file if you are willing to _know_ what the file is like.
  typically, hwoever, you would include metainformation that is not needed
  once it has been processed and is in memory, versioning information, some
  form of validation clues for the information (array bounds, etc), and in
  all likelihood if you store binary data, some compression technique.
  many arguments to the contrary notwithstanding, binary representation,
  when it has been made to work, is _incredibly_ bloated compared to what
  people set out believing it will be.  making binary representation
  efficient is so hard that most people give up, satisfied with gross
  inefficiency.  a Microsoft Word document is the typical example of how
  unintelligently things _can_ be done when the real dunces are let at it.

  you may actually be better off writing your vector of 4-bit bytes out as
  hexadecimal digits, pretending that it is a huge number.  Common Lisp
  does not offer you any _huge_ help in hacking such notations back to more
  common internal representations, but actually trying to time the work you
  do during I/O has left many programmers bewildered by the cost of such a
  simple operation.  a disk read can easily take millions of times longer
  than a memory read.  whether you decode digits in that time or map bits
  directly into memory is completely irrelevant to the system performance.

  the conditions under which these low-level things matter are so different
  from what normal people experience that they will have studied the topic
  of internal and external representation very carefully before they need
  to know the details.

| Allegro is my vendor.

  well, no, Franz Inc is the vendor behind Allegro CL.

Sheesh.

  well, if they tend to be rare, I'd have expected some _justification_ for
  the implicit expectation that this was one of those rare cases.

  however, to zoom out a bit, if people in the Common Lisp community wonder
  why there's so (comparatively) little communal development activity, do
  consider the responses received to the work that _is_ being done when it
  is published.  as far as I have seen, the response is generally "thanks.
  now where's the rest?", no matter how much you do.  it almost sounds like
  a Norwegian tax collector, one of nature's strongest de-motivating forces.

Our intention in putting this proposal out is to solicit
technical reactions to the merits and flaws of the design,
and to solicit suggestions for improvement.  As a document,
it will have a copyright, but as an api spec - well, I don't
think it's possible to copyright an api.  The ideas, once
broadcast, will become public and thus anyone could submit a
modified proposal as their own, if they wanted to.

As for X3J13, the proposal may come to be appropriate for submission
eventually, but we're certainly not there yet and are taking this
one step at a time.

  I'm happy that you, too, consider Marco Antoniotti's response _rude_
  towards Franz Inc, and that you support my point: if you suspect the
  worst of motives when you receive a gift from somebody, other people
  generally don't give you much _more_ for free from then on.

  as for rudeness in this particular case, maybe you just need to learn to
  live with the fact that people find _you_ rude and _disgusting_ to deal
  with when you don your halo and fight to save the world from a rudeness
  you find only when _you_ make worst-case assumptions about the motives of
  others, but I guess that's OK since you do it, wearing that halo.  I wish
  you had learned something, but you really learned _nothing_ from the last
  time we had this discussion.  *sigh*

  and if you are such a champion of benefit of the doubt, consider making
  some actions of yours conform to your self-serving claims some day.  it
  would be a little less disgusting to behold a reeking hypocrite actually
  follow his _own_ advice once in a while, at least.

As usual the problem is "what happens if Harlequin decides that Franz
proposal is not-what-they-wanted and vice-versa".  Then we may end up
with two different implementations for I/O stuff and the whole Common Lisp
community suffers.

Cheers

Cheers

--
((( DANGER )) LISP BIGOT (( DANGER )) LISP BIGOT (( DANGER )))

Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1                   email: matomira AT acm DOT org
CH-2007 Neuchatel                 tel:       +41 (32) 720-5157
Switzerland                       FAX:       +41 (32) 720-5720

also, thanks for all the replies.

andrew

We have made good use of the Gray streams proposal for the last 10
years.  Others have started using it more recently, and it has served
us all well.  But there are several problems with the proposal, and
we have a good idea as to how to do I/O better in several ways.  This
new proposal that we will make available encapsulates those ideas.

If the ideas that this proposal espouses are completely wrong, then
it will become clear in the process of being made public.  But if
these ideas catch on, then they will be implemented, whether portably
or not, and the whole Lisp community will win, not suffer.

One other aspect of this: Franz has the choice of how to disseminate
this proposal.  We could just play the cards close and show it first
at our next release.  Or, we could show it sooner and allow both the
community and ourselves to benefit from the ensuing dialog.  We have
chosen the latter approach.

Unlike Erik, I will not spank you now, even if that is what you
want.