The Unix Heritage Society mailing list
 help / color / mirror / Atom feed
[parent not found: <1FD28B19-FA50-4581-BB0A-257B5DDE1890@kdbarto.org>]
* [TUHS] termcap vs terminfo
@ 2015-01-06 21:32 Mary Ann Horton
  0 siblings, 0 replies; 16+ messages in thread
From: Mary Ann Horton @ 2015-01-06 21:32 UTC (permalink / raw)


Quoting Dan Cross <crossd at gmail.com>:

> On Tue, Jan 6, 2015 at 12:33 PM, Johnny Billquist <bqt at update.uu.se> wrote:
>
>> On 2015-01-06 17:56, Dan Cross wrote:
>>>
>>> I believe that Mary Ann is referring to repeatedly looking up
>>> (presumably different) elements in the entry.  Assuming that e.g. `vi`
>>> looks up O(n) elements, where $n$ is the number of elements, doing a
>>> linear scan for each, you'd end up with quadratic behavior.
>>>
>>
>> Assuming that you'd look up all the elements of the termcap entry at
>> startup, and did each one from scratch, yes.
>
>
> Yes.  Isn't that exactly what Mary Ann said was happening?  :-)

Yes

> But that would beg the question, why is vi doing a repeated scan of the
>> terminal entry at startup, if not to find all the capabilities and store
>> this somewhere? And if doing a look for all of them, why not scan the
>> string from start to finish and store the information as it is found? At
>> which point we move from quadratic to linear time.
>>
>
> I don't think she said it did things intelligently, just that that's how it
> did things.  :-)
>
> But now we're getting into the innards of vi, which I never looked at
> anyway, and I guess is less relevant in this thread anyway.

vi does indeed look up all the various capabilities it will need,
once, when it starts up.  It uses the documented interface, which
is tgetent followed by tgetstr/tgetnum/tgetflag for each capability.
tgetent did a linear search.

>> The short of it (from what I got out of it) is that the move from termcap
>> to terminfo was mostly motivated by attribute name changing away from fixed
>> 2 character names.
>>
>> A secondary motivation would be performance, but I don't really buy that
>> one. Since we only moved to terminfo on systems with plenty of memory,
>> performance of termcap could easily be on par anyway.
>>
>
> I tend to agree with you and I'll go one further: it seems that frequently
> we tend to identify a problem and then go to 11 with the "solution."  I can
> buy that termcap performance was an issue; I don't know that going directly
> to hashed terminfo files was the optimal solution.  A dbm file of termcap
> data and a hash table in whatever library parsed termcap would go a long
> way towards fixing the performance issues.  Did termcap have to be
> discarded just to add longer names?  I kind of tend to doubt it, but I
> wasn't there and don't know what the design criteria were, so my
> very-much-after-the-fact second guessing is just that.

It's been 30+ years, so the memory is a little fuzzy.  But as I recall,
I did measure the performance and that's how I discovered that the
quadratic algorithm was causing a big performance hit on the hardware
available at the time (I think I was on a VAX 11/750, this would have
been about 1982.)

I was making several improvements at the same time.  The biggest one
was rewriting curses to improve the screen update optimization, so it
would use insert/delete line/character on terminals supporting it.
Cleaning up the mess termcap had become (the format had become horrible
to update, and I was spending a lot of time making updates with all
the new terminals coming out) and improving startup time (curses also
had to read in a lot of attributes) were part of an overall cleanup.
IIRC, there may also have been some restrictions on parameters to string
capabilities that needed to be generalized.

Hashing could have been done differently, using DBM or some other method.
In fact, I'd used DBM to hash /etc/aliases in delivermail years earlier
(I have an amusing story about the worlds slowest email I'll tell some
other time) but at the time, it seemed best to break with termcap
and go with a cleaner format.




^ permalink raw reply	[flat|nested] 16+ messages in thread
* [TUHS] termcap vs terminfo (was: I swear! I rtfm'ed)
@ 2015-01-01 17:04 Warner Losh
  2015-01-02 19:13 ` Erik E. Fair
  0 siblings, 1 reply; 16+ messages in thread
From: Warner Losh @ 2015-01-01 17:04 UTC (permalink / raw)



> On Jan 1, 2015, at 9:21 AM, Johnny Billquist <bqt at update.uu.se> wrote:
> 
> On 2015-01-01 17:11, Mary Ann Horton<mah at mhorton.net> wrote:
>> 
>> The move was from termcap to terminfo.  Termlib was the library for termcap.
> 
> Doh! Thanks for the correction. Finger fart.
> 
>> There were two problems with termcap.  One was that the two-character
>> name space was running out of room, and the codes were becoming less and
>> less mnemonic.
> 
> Ah. Yes, that could definitely be a problem.
> 
>> But the big motivator was performance.  Reading in a termcap entry from
>> /etc/termcap was terribly slow.  First you had to scan all the way
>> through the (ever-growing) termcap file to find the correct entry.  Once
>> you had it, every tgetstr (etc) had to scan from the beginning of the
>> entry, so starting up a program like vi involved quadratic performance
>> (time grew as the square of the length of the termcap entry.)  The VAX
>> 11/780 was a 1 MIPS processor (about the same as a 1 MHz Pentium) and
>> was shared among dozens of timesharing users, and some of the other
>> machines of the day (750 and 730 Vaxen, PDP-11, etc.) were even slower.
>> It took forever to start up vi or more or any of the termcap-based
>> programs people were using a lot.
> 
> Hum. That seems like it would be more of an implementation issue. Why wouldn't you just cache all the entries for the terminal once and for all? terminfo never came to 16-bit systems anyway, so we're talking about systems with plenty of memory. Caching the terminal information would not be a big memory cost.

BSD solved this problem that way: parse /etc/termcap and put all the entries into termcap.db. :)

Warner

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20150101/ae4a3d87/attachment.sig>


^ permalink raw reply	[flat|nested] 16+ messages in thread

end of thread, other threads:[~2015-01-12 15:36 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <mailman.143.1420561935.3354.tuhs@minnie.tuhs.org>
2015-01-06 16:51 ` [TUHS] termcap vs terminfo Johnny Billquist
2015-01-06 16:56   ` Dan Cross
2015-01-06 17:33     ` Johnny Billquist
2015-01-06 17:53       ` Dan Cross
     [not found] <1FD28B19-FA50-4581-BB0A-257B5DDE1890@kdbarto.org>
2015-01-10 22:15 ` [TUHS] Termcap " David Barto
2015-01-10 22:43   ` Lyndon Nerenberg
2015-01-10 22:51     ` Lyndon Nerenberg
2015-01-10 23:02     ` Christian Neukirchen
2015-01-10 23:04       ` Lyndon Nerenberg
2015-01-11 16:48         ` Christian Neukirchen
2015-01-11  2:06     ` Dave Horsfall
2015-01-11  9:16       ` Diomidis Spinellis
2015-01-12 15:36       ` Clem Cole
2015-01-06 21:32 [TUHS] termcap " Mary Ann Horton
  -- strict thread matches above, loose matches on Subject: below --
2015-01-01 17:04 [TUHS] termcap vs terminfo (was: I swear! I rtfm'ed) Warner Losh
2015-01-02 19:13 ` Erik E. Fair
2015-01-05  7:06   ` Peter Jeremy
2015-01-06  0:40     ` John Cowan
2015-01-06 12:22       ` arnold
2015-01-06 16:02         ` [TUHS] termcap vs terminfo Mary Ann Horton
2015-01-06 17:12           ` arnold

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).