Walt Karas's Home Page
Last update: February 16, 2024
You can e-mail me at wkaras dot yahoo dot com . Entiendo español si prefiere escribirme en español. Please feel free to re-host any or all of the material on this page if you so desire. (Do not remove copyright notices.)
Photos of my late wife Carmen with Pope John Paul II : first second
Paintings
Some paintings by my wife's niece, Patricia Galeazzi-Henry.
Website with paintings by my friend from college.
My Background
I live in Champaign, Illinois in the United States. I have a Bachelor's degree in Computer Science and Math from Eastern Michigan University (also the alma mater of Judge Greg Mathis). I have 30+ years of experience as a software developer, mostly in embedded and low-level software. I have several repositories on github and two blogs on Quora . I am also on Linkedin . I am on stackoverflow and stackoverflow en español .
C++ Library Bit Fields
I have written a bit field facility provided by the header file bitfield.h ( https://github.com/wkaras/C-plus-plus-library-bit-fields ). The facility is more portable and flexible than the bit field facility provided by the base language. Bit field structures can be laid out from most to least or least to most significant bits, under programmer control. Bit field structures can be located in device registers that are not memory mapped. With good compiler optimization, the performance is comparable.
Heap Memory Manager
A very portable C-language Heap Memory Manager (Dynamic Memory Allocator). To check it out, the documentation is here, and the code is at https://github.com/wkaras/heap-memory-manager .
Here is a web site that describes a interesting algorithm (TLSF) for C-style dynamic memory allocation. This algorithm should be significantly faster than the one I used. Instead of using best-fit, this algorithm finds a free block whose size is within 2/31 or 2/63 (tunable) of the size of the requested block. Even best-fit can waste some memory (because there can be free blocks too small to be useful to the application). Therefore, the trade-off made by this algorithm may be desirable. The provided implementation, however, does not seem to me to be that easy to port.
One important thing I neglected to mention/realize is that the audit tests can result in a read of a bad address, which in some environments will cause an internal interrupt. If you see this, it's not a reason to be concerned that heapmm won't work in your environment.
To reduce memory space overhead, this allocator uses the memory within free blocks to create a searchable data structure (an AVL tree) of free blocks. The potential big trade-off with that is it will result in a lot of memory accesses with terrible locality. That is, a low ratio of number of memory accesses to number of memory pages containing the accessed addresses. This could be a significant problem for an application that uses a large amount of dynamically allocated memory, and runs in an environment with insufficient physical memory that it can run without page faults. Lack of locality can also have an effect even if memory pages are not paged out to and back from secondary storage. On higher-end Freescale processors, for example, the Memory Management Unit (MMU) can be useful even if there is no actual paging of memory. But the MMU uses a large table in physical memory that defines the mapping of virtual memory pages to physical memory pages. The MMU is only able to cache a limitied number of entries in this table. So an access to a memory page whose translation table entry is not cached will cause two memory accesses, one to load in the translation entry, followd by the actual access itself. So this case, bad locality of memory accesses can have a price even without memory paging.
Locality of course also applies to memory caching. But since cache lines are small (typically 8 to 16 bytes I think), I can’t see a way to design a general purpose heap memory manager so it’s locality with respect to memory caching would not be low.
This allocator, as is, is obsolete now because it is not multithread-safe. This could perhaps be used for per-thread memory polls. If memory was deallocated in a different thread than it was allocated, it could be put in a linked list associated with the allocating code. When the allocation function is called in a thread, it could pop all the blocks that had been put in its associated linked list, and put them into its memory pool, before doing the allocation. The head pointers for the free lists would have to be atomic, and versioned due to the ABA problem. Unfortunately, portable versioned pointers are not straight-forward: ver_ptr.h
Memory Game
To download a zip file containing my Memory Game program (created with Visual C++ .NET), click here. To view the source code, click here .
The executable is in the public domain. I wrote this program in order to learn Visual C++ .NET, but it might be of some interest to very young children and extremely bored people. The borders on the "Play Again" and "Exit" buttons at the end of the game are not drawn properly. (If you minimize, then restore the form, the border on the "Play Again" button changes.) But I think this has to be Microsoft's bug, not mine. You may also notice that, when the prompt says you can click "anywhere" to continue, a click on the text of the prompt is ignored. This is because the prompt is associated with a Label object. Label is derived from the Control class, so it receives clicks, even though it does nothing with them. I decided it wasn't worth the trouble to display the text directly without using a control, so that a click on the text would not be ignored.
AVL Tree Template
I have written a C++ template that encodes the AVL Tree algorithms in a very flexible way. To check it out, click here. This, plus instrusive singly and doubly linked list and hash table templates are available (with MIT open source license) here.
I have also written an equivalent "generic package" in straight C. (Or, download a zip file with the HTML documentation and source files.) It would be fairly straightforward to use this generic package to create a facility in C that would be analogous to the map/set templates in the C++ Standard Template Library (where items are copied into the container instead of linked in, and the container allocates memory from the heap to hold the copies). Used by heap memory manager above and by Minix .
The AVL Tree implementations are dedicated to the Public Domain. (I can provide it under an MIT license if need be.)
CUI Chess
Here is a chess program that I wrote for MS-DOS back in the mid 90s:
description zip file with MS-DOS executable zip file with MS-DOS source code port to UNIX xterm
Here is a port to run in a UNIX xterm: https://github.com/wkaras/xterm-CUI-Chess
This program acts really stupid in end-games when it has two pieces and the opponent only has their king.
I have not managed to beat the program (with any reasonable look-ahead enabled). But I am a lousy chess player. For those who have beaten it, I’d love it if you sent me the move sequence and what command line parameters you used at startup. Let me know if I can make public the move sequence and/or your name.
Portable Spinlock Code in C
Here is the header file and the implementation file . This code is untested, so if you find problems with it, let me know. Peterson's Algorithm is a simpler, 2-way mutual exclusion algorithm. Lamport's Bakery Algorithm , published back in the 70s, is a slightly more complex n-way mutual exclusion algorithm, which has some useful properties that my algorithm does not. Unlike mine, Lamport's algorithm is "fair" in that processors get the mutex in the order that they requested it. On the other hand, if the processors are unavoidably contending that much for the same shared resource, you may be wasting your money paying for multiple processors. To observe a very minor point, adapting Lamport's algorithm to handle ticket number wrap-around (due to precision limits) would I think have to involve giving "cuts" in the line. (The more fairness matters, the more likely it is ticket number wrap-around will happen.) I believe that Lamport found in later investigation that his algorithm works even if overlapping memory accesses of any single memory location by multiple processors caused one or both accesses to fail (not just be arbitrarily ordered). This is not the case with my algorithm.
WARNING: I think I may have developed this code and algorithm while I was in the employ of Alcatel (now part of Nokia), so Nokia could potentially claim it as its intellectual property. If you want to avoid this issue, and need a multi-way spinlock, use Lamport’s Algorithm. Another alternative for a multi-way spinlock is a well-know technique using a “binary tree” of Peterson 2-way locks, but (like my algorithm) it lacks the fairness of Lamport’s Algorithm. If anyone really cares, I could try to get it clarified whether Alcatel-Lucent feels any burning desire to assert rights over this.
"Item List" Programming Technique
Click here to see some example code.
Odds and Ends
This stuff's in the public domain.
Convert hex numbers to decimal...
Delaware Sucks
Don't go to Delaware if you can help it: Shakedown by the Delaware State Police .
How to Store Christmas Lights
Save some sturdy cardboard tubes, such as those that are left when rolls of wrapping paper are used up. Wind the lights in a spiral around a tube, without overlapping, and secure the ends with masking tape. From a plastic bottle, cut a piece of plastic that will cover the end of the cardboard tube with lots of overlap. Cut a length of strong twine that is about twice the length of the cardboard tube. Make a whole in the center of the piece of plastic that is just big enough to thread the twine through. Thread one end of the twine through the hole, then make a knot at the end of twine. The knot must be too large to pass through the hole in the plastic. Pass the other end of the twine through the cardboard tube. Tie a loop in the (unknotted) end of the twine. You can now hang the tube with the lights in a convenient storage place by putting the loop over a nail or peg.
Links
Translate between English and other major European languages...
vi for Windows PCs... Please DON'T e-mail me to tell me about all the wonderful editors I could use instead. Vi burns out the good-editor pleasure centers in the brains of its long-term users, so there is no point in us switching editors now.
C++ source code obfuscator... (shrouder)
The "Empty Member" C++ Optimization... (My C++ AVL tree template now uses this.)
Chambana, IL Area Links
Raleigh, NC Area Links
Jordyn the MUA (make-up artist)
Vic's Italian Restaurant and Pizzeria
Torero's (Mexican restaurant)
