Standard Libraries

[SoulofDeity]

I'm just gonna sum up everything in 1 sentence. "I don't care about what's standard, I care about what is most efficient and understandable."


I created this topic more or less to discuss with people where many improvements could be made in all libraries (including C standard libraries). Instead of just bashing my idea, tell me where improvements can be made.


btw, just noticed the topic name change

SoulofDeity, I'm interested in your memory interface.

I'm currently implementing my userspace memory allocation routines and am following the Posix spec. Do you have any improvements in mind ? The only difference I can see is using u64 for size. I can't use this because 64 bit ints are inefficient on some of the processors I target. Are there any other improvements you can suggest ?

stick peanut butter in all of your devices peripheral ports.

[Griwes]

I'm just gonna sum up everything in 1 sentence. "I don't care about what's standard, I care about what is most efficient and understandable."

I created this topic more or less to discuss with people where many improvements could be made in all libraries (including C standard libraries). Instead of just bashing my idea, tell me where improvements can be made.

btw, just noticed the topic name change

Standard was created during many discussions, and we already had C89, C90, C99, C11, C++98, C++03 and C++11 (mentioning both C and C++, because well, they are a bit connected and influencing each other), with more of them incoming. Do you really think that you can do better than something that has been worked on since ever in shorter time? I agree, many things in standard are not too easy to understand, some things can be improved - but to get real improvement, you need some heavier change than using non-standard and non-obvious type called u64 (is it always *exactly* 64 bits, aka uint64_t? use uint64_t. Is it at least 64 bits, aka uint_least64_t? use uint_least64_t etc.), than actually impacts something.

And you need to think about it for a long time, follow standard guidelines, submit a proposal and wait for smarter and/or more knowledgeable people to discuss it for the next standard. Other ways don't work, because you will end up with messy, but also poorly designed libraries, reimplementing messy libraries, which is worse than just messy libraries.

[Combuster]

I don't care about what's standard, I care about what is most efficient and understandable.

Point was and still is, deviating from the standard is inefficient in terms of people needing to learn a new one, and less understandable for the very same reason. Your custom implementation will need to be a real lot more efficient and understandable to cover up for the losses created by your own hands.

But in general, your overall attitude is simply asking for some time to screw up all by yourself to realize what this lesson is about. And then perhaps a few times again if the dent in your ego wasn't large enough to learn the more important lesson recursively embedded in this post. Good luck.

[SoulofDeity]

I don't care about what's standard, I care about what is most efficient and understandable.

Point was and still is, deviating from the standard is inefficient in terms of people needing to learn a new one, and less understandable for the very same reason. Your custom implementation will need to be a real lot more efficient and understandable to cover up for the losses created by your own hands.

But in general, your overall attitude is simply asking for some time to screw up all by yourself to realize what this lesson is about. And then perhaps a few times again if the dent in your ego wasn't large enough to learn the more important lesson recursively embedded in this post. Good luck.

My ego isn't dented at all. I don't know any of you and couldn't care less what you think of me. If anything, everyone here has been looking down on me and insulting me from the start. Just because I'm new to the community doesn't mean I'm ignorant.

Anyway, I can obviously see that this isn't the site to share my ideas, so I won't bother contributing anymore. Later people

[bluemoon]

I see you ignored negative (and constructive) feedbacks.

Perhaps you are looking for motivations but not opinions.

By the way, if you really need it, Good idea, go ahead.

When I post a design concept here, I want people to pry it apart, because it gives me valuable feedback on weaknesses I might have overlooked. I consider it a trait of experienced developers not to take personal offense when an idea of theirs is shot down.

Think about this.

[Combuster]

If anything, everyone here has been looking down on me and insulting me from the start.

On Not Reacting Like A Loser

Odds are you'll screw up a few times on hacker community forums — in ways detailed in this article, or similar. And you'll be told exactly how you screwed up, possibly with colourful asides. In public.

When this happens, the worst thing you can do is whine about the experience, claim to have been verbally assaulted, demand apologies, scream, hold your breath, threaten lawsuits, complain to people's employers, leave the toilet seat up, etc. Instead, here's what you do:

Get over it. It's normal. In fact, it's healthy and appropriate.

I hope you may one day realize what nonsense you just said.

[qw]

If anything, everyone here has been looking down on me and insulting me from the start.

This is blatantly untrue. Maybe you feel insulted, but nobody has called you names. People have criticized your ideas, your choices and your attitude, but not your person. Now pull yourself together and stop behaving like a child.

[Brendan]

Hi,

Ways that (in my opinion) these functions could be improved:

• The mount() and unmount() functions do operations that only very specialised pieces of software should be able to do (e.g. the OS's virtual file system and/or "administrator only" utilities ). For this reason they probably shouldn't be included in a standard library intended for normal application developers.
• I like the idea of returning an error code directly from functions (e.g. "openDirectory()"); however these error codes need to be standardised and documented. Note: mostly I think "errno" in the C standard library was a mistake and the only reason it still exists is because they can't fix it now without breaking older software (e.g. it made sense when they invented it because software was single-threaded, but is "less good" for multi-threaded software because it requires thread local storage to implement)
• the functions to close a directory, close a file and delete a file should all return an error code too. For example, if you do "closeDirectory(NULL);" then it should return an "ERROR_YOU_ARE_DRUNK" error code. Of course deleting a file might return things like "file not found". Closing a file normally means flushing any buffers, etc; which means closing a file might cause "out of disk space" errors.
• I'm not sure if "u32 openDirectory(Directory *dir, char *path)" should be "u32 openDirectory(Directory **dir, char *path)".
• Various structures need to be defined (e.g. the "DirectoryEntry" structure).
• For "fileSeek()", the "u32 seekStart" parameter is too small. Basically it limits the maximum file size to 4 GiB, which is too small for a lot of common things (e.g. backups).
• For all of the functions for reading and writing to files; the buffer parameter should be "u8 *buffer" and not "void *buffer". The reason for this is that it forces programmers to think about serialising output correctly and de-serialising input (and doing parsing/error checking) correctly. For the same reason (and other reasons already mentioned by other people) I wouldn't have the "endian conversion" versions at all.
• It's a sad fact, but a lot of programmers now are "web monkeys". Bloating things up with "plain text", then failing to do any sanity checking and choking on the first malformed UTF-8 character is all they know. For this reason I would consider providing text file IO functions. These functions would mostly just be wrappers around the normal (binary) file IO that take care of reading/writing individual characters, reading/writing lines of characters, etc. However, these functions would have built in "anti-moron protection" features; like discarding byte order marks and '\r' characters, returning errors if invalid UTF-8 is detected, returning errors if valid but illegal characters (like "delete", "backspace", zero, etc) are detected, etc.

That's about all I can think of for the functions you've described. There's a lot missing - string handling, time and date functions, fork/exec or spawning (or both?), command line args, environment variable access, more memory management (e.g. memory mapped files), IPC and/or signals or something, networking, maths, etc.


Cheers,

Brendan

[bewing]

This is a difficult topic, and I agree with many of the things that SoulOfDeity and Brendan say. I never liked that the C std lib used "int"s for args. I can't tell you how many nightmares that has caused me on old 16 bit machines, in the olden days. Standard args in standard libs MUST be fixed-sized, and BIG -- as Brendan says, seek fns, memory alloc fns, and IO fns must have 64bit sizes.

size_t, errno, and all the other damned "_t"s piss me off, too. If you are going to make a standard, then don't add a lot of extraneous punctuation to everything.

For efficiency, I would also add multiple versions of memset and memcpy that have args that are bigger than bytes and require alignment.

On the other hand, while the C standard lib has been bloated somewhat, and is not as pretty as it could be ... the big problems are in all the other libs that were never standardized. Look at the horrifying number of unshared "shared object libs" that almost every linux app requires. Imagine the savings if 500 of those .SOs could be standardized into one single nice library.

[Owen]

This is a difficult topic, and I agree with many of the things that SoulOfDeity and Brendan say. I never liked that the C std lib used "int"s for args. I can't tell you how many nightmares that has caused me on old 16 bit machines, in the olden days. Standard args in standard libs MUST be fixed-sized, and BIG -- as Brendan says, seek fns, memory alloc fns, and IO fns must have 64bit sizes.

Memory functions and I/O read/write functions should take size_ts for length. No point using a 64-bit number there when you only have 16-bit addresses...

Admittedly, fseek's use of "long int" is horrid, and it should be "off_t"; this is unfortunate. Defining off_t to be 64-bit would be unwise, however; C has to run on everything from 8-bit microcontrollers to 64-bit machines; it is very unlikely an 8-bit microcontroller needs 64-bit files.

Additionally, you're assuming that the target system has a 64-bit type. C makes no such assumptions ((u)intN_t are all optional: uintN_least_t and uintN_fast_t however are both mandatory)

size_t, errno, and all the other damned "_t"s piss me off, too. If you are going to make a standard, then don't add a lot of extraneous punctuation to everything.

It's a matter of taste (_t) and history (errno).

For efficiency, I would also add multiple versions of memset and memcpy that have args that are bigger than bytes and require alignment.

Are they really necessary? The fastest implementation of memset is already rep stosb on modern CPUs

On the other hand, while the C standard lib has been bloated somewhat, and is not as pretty as it could be ... the big problems are in all the other libs that were never standardized. Look at the horrifying number of unshared "shared object libs" that almost every linux app requires. Imagine the savings if 500 of those .SOs could be standardized into one single nice library.

Bloated? Seriously?!
Byte/multibyte string, wide string, integer, float, time, basic I/O and threading support is bloated to you?!

The C standard library is very much a case of providing the base essentials that every application requires, that are absolutely portable.

Or perhaps you are mixing up the C standard library and the POSIX standard library (confusingly named libc)?

[bewing]

If you cannot depend on a size_t being more than 1 byte, then you need to rewrite every piece of your code to do IO in chunks smaller than 256 bytes, for portability. Except if size_t happens to be defined as signed, then you have to limit IO to less than 128 bytes. And all your dynamic memory allocations, too. I dare you to try to rewrite all the code you've ever written so that it's truly portable onto 8 bit machines. And the fact that most machines in past history don't really support 64bit values is irrelevant. The functions should take pointers to 8 byte memory addresses as args. That's universally supported.

The fastest implementation of memset is already rep stosb on modern CPUs

Only on x86 CPUs that are not using vectorization -- we are trying to be architecture independent here. And in any case, I often would like to memset a big chunk of memory to a 32bit pattern -- 0x11223344. Arrays of 32bit and 64bit values need to be initted sometimes, you know.

Bloated? Seriously?!

Newlib has over 400 functions. That's already too many. Of course, Glibc has an order of magnitude more than that. And everyone tries not to use the string functions, because they are not "safe". So there is an entire extra semi-standard set of those .... Similarly with printf and scanf .... And on and on.

[Brendan]

Hi,

Memory functions and I/O read/write functions should take size_ts for length. No point using a 64-bit number there when you only have 16-bit addresses...

There should be no reason why you can't seek to the 1234567890123456th byte of a file, and then read 12 bytes at that position on an 8-bit CPU (e.g. perhaps something using NFS). Also note that all 8-bit CPUs that I'm aware of are capable of supporting things like 512-bit or larger addition (just not with a single instruction - you need to chain multiple "ADD/ADC" instructions together), so doing basic operations for 64-bit types is just slower (and far from unsupportable).

Additionally, you're assuming that the target system has a 64-bit type. C makes no such assumptions ((u)intN_t are all optional: uintN_least_t and uintN_fast_t however are both mandatory)

Ideally, you'd want to use the "uint64_fast_t" type for 64-bit arithmetic, and shouldn't use "uint64_t" unless you're dealing with things that have exact requirements (e.g. hardware devices, files or network packets). Of course nobody actually uses "uint64_fast_t" because it makes your fingers fall off and your eyes bleed, but if you were creating a new standard you could avoid that (e.g. "u64").

I'd also point out that if someone (e.g. perhaps the original poster) was interested in endian conversions; then it might be sane to ban "endian-unknown" exact size types (like "uint64_t") and replace them with "endian-specific" exact size data types (e.g. "u64_be" and "u64_le"). This makes sense, because for all these cases where you actually need exact size integers you also need to get the endian-ness right.

The fastest implementation of memset is already rep stosb on modern CPUs

Only on x86 CPUs that are not using vectorization -- we are trying to be architecture independent here. And in any case, I often would like to memset a big chunk of memory to a 32bit pattern -- 0x11223344. Arrays of 32bit and 64bit values need to be initted sometimes, you know.

This depends what you're doing. In general, people who think that they're writing optimised versions of memset/memcpy test their optimised versions on idiotically huge memory sizes (e.g. 128 MiB or more); while well written code rarely sets of copies anything larger than about 4 KiB (about 20 bytes seems to be the sweet spot). The end result is that the SSE/AVX optimised versions are good for things that are irrelevant but suck (due to excessive startup overhead) for well written code.


Cheers,

Brendan

[Owen]

If you cannot depend on a size_t being more than 1 byte, then you need to rewrite every piece of your code to do IO in chunks smaller than 256 bytes, for portability. Except if size_t happens to be defined as signed, then you have to limit IO to less than 128 bytes. And all your dynamic memory allocations, too. I dare you to try to rewrite all the code you've ever written so that it's truly portable onto 8 bit machines. And the fact that most machines in past history don't really support 64bit values is irrelevant. The functions should take pointers to 8 byte memory addresses as args. That's universally supported.

See C11 7.20.3:2 to see why your argument is a great big pile of twaddle (namely: SIZE_MAX >= 65535, size_t is unsigned)

As for the size of file offsets: A microcontroller with 128kB of flash gets no utility from 64-bit file offsets. The operating system/OS standard (e.g. POSIX) could define the minimum size of this (in fact POSIX does)

The fastest implementation of memset is already rep stosb on modern CPUs

Only on x86 CPUs that are not using vectorization -- we are trying to be architecture independent here. And in any case, I often would like to memset a big chunk of memory to a 32bit pattern -- 0x11223344. Arrays of 32bit and 64bit values need to be initted sometimes, you know.

On recent x86, rep stosb transfers whole cache lines. Try beating that....

I can't argue against the utility of "memset16/memset32", but their necessity is less so. The C standard library is not designed to offer the most efficient version of everything: It's designed to offer the base requirements of every application in a concise, compact library which is available absolutely everywhere

Bloated? Seriously?!

Newlib has over 400 functions. That's already too many. Of course, Glibc has an order of magnitude more than that. And everyone tries not to use the string functions, because they are not "safe". So there is an entire extra semi-standard set of those .... Similarly with printf and scanf .... And on and on.

Newlib and Glibc are not implementations of the C standard library. They're implementations of the POSIX standard library - a large superset which also contains all sorts of obsoleted antiquitated crap and/or UNIXy assumptions.

Don't tar the C standard with the POSIX feather.

Hi,

Memory functions and I/O read/write functions should take size_ts for length. No point using a 64-bit number there when you only have 16-bit addresses...

There should be no reason why you can't seek to the 1234567890123456th byte of a file, and then read 12 bytes at that position on an 8-bit CPU (e.g. perhaps something using NFS). Also note that all 8-bit CPUs that I'm aware of are capable of supporting things like 512-bit or larger addition (just not with a single instruction - you need to chain multiple "ADD/ADC" instructions together), so doing basic operations for 64-bit types is just slower (and far from unsupportable).

I said lengths, not offsets. I still argue that not every machine C supports warrants 64-bit file offsets - that doesn't mean that "further refined" standards can't define off_t to be so

Additionally, you're assuming that the target system has a 64-bit type. C makes no such assumptions ((u)intN_t are all optional: uintN_least_t and uintN_fast_t however are both mandatory)

Ideally, you'd want to use the "uint64_fast_t" type for 64-bit arithmetic, and shouldn't use "uint64_t" unless you're dealing with things that have exact requirements (e.g. hardware devices, files or network packets). Of course nobody actually uses "uint64_fast_t" because it makes your fingers fall off and your eyes bleed, but if you were creating a new standard you could avoid that (e.g. "u64").

I agree that the naming is unfortunate ("ufast64_t"/"uleast64_t" or such would have been a much better choice while maintaining the existing naming conventions

[SoulofDeity]

Wow...I was under the assumption that everyone just thought I was ignorant for even suggesting a new standard. Never thought I'd start a debate :S


Anyway, I came back because I was wanting to share one of the new libraries I wrote for lists. Take a look and tell me what you think.

Here's the header file:

Code: Select all

/* list.h		Header file for List Functions
 * author:		SoulofDeity
 *
 * Comments:
 *	You can use this for whatever you want, no need for credit,
 *	just don't claim it as your own work.
 *************************************************************************/
#ifndef __LIST_H__
#define __LIST_H__

#include <stdint.h>
#include <string.h>
#include <malloc.h>


typedef struct {
   uint32_t count;
   uint32_t itemSize;
   void *item;
} List;


List *lnew(uint32_t count, uint32_t itemSize);
void ldestroy(List *list);
void *lresize(List *list, uint32_t count);
void lclear(List *list);
void *ladd(List *list, void *item);
void *linsert(List *list, uint32_t index, void *item);
void lremove(List *list, uint32_t index);
void lremoveLast(List *list);
void *lget(List *list, uint32_t index);
void *lset(List *list, uint32_t index, void *item);

/* alternative naming for ladd and lremoveLast
 *************************************************************************/
#define lpush(l, v)		ladd(l, v)
#define lpop(l)			lremoveLast(l)

/* same instructions, but with type cast
 *   eg. lgetc(uint32_t, list, 0) would return the first value in 'list'
 *       as a uint32_t (32-bit unsigned integer)
 *************************************************************************/
#define laddc(t, l, v)		((t *)lresize(l, l->count + 1))[0] = v
#define linsertc(t, l, i, v)	((t *)linsert(l, i, l))[0] = v
#define lpushc(t, l, v)		((t *)lresize(l, l->count + 1))[0] = v
#define lgetc(t, l, i)		((t *)lget(l, (i)))[0]
#define lsetc(t, l, i, v)	((t *)lget(l, (i)))[0] = v


#endif /*** __LIST_H__ ***/

Source File

Code: Select all

/* list.c		Source file for List Functions
 * author:		SoulofDeity
 *
 * Comments:
 *	You can use this for whatever you want, no need for credit,
 *	just don't claim it as your own work.
 *************************************************************************/
#include "list.h"


List *lnew(uint32_t count, uint32_t itemSize) {
   List *list = (List *) malloc(sizeof(List));
   if (!list) return NULL;
   list->itemSize = itemSize;
   if (!count) {
      list->count = 0;
      list->item = NULL;
      return list;
   }
   list->count = count;
   list->item = malloc(count * itemSize);
   if (!list->item) {
      free(list);
      return NULL;
   }
   return list;
}

void ldestroy(List *list) {
   if (!list) return;
   if (list->count) free(list->item);
   free(list);
}

void *lresize(List *list, uint32_t count) {
   if (!list) return NULL;
   if (list->count == count)
      return list->item + (list->count - 1) * list->itemSize;
   if (!count && list->count) {
      list->count = 0;
      free(list->item);
      return NULL;
   }
   if (!list->count & count) {
      list->item = malloc(count * list->itemSize);
      if (!list->item) {
         list->count = 0;
         return NULL;
      }
   } else {
      list->item = realloc(list->item, count * list->itemSize);
      if (!list->item) {
         list->count = 0;
         return NULL;
      }
   }
   list->count = count;
   return list->item + (list->count - 1) * list->itemSize;
}

void lclear(List *list) {
   if (!list) return;
   if (!list->count) return;
   list->count = 0;
   free(list->item);
}

void *ladd(List *list, void *item) {
   if (!list) return NULL;
   list->count++;
   if (list->count == 1) {
      list->item = malloc(list->itemSize);
      if (!list->item) {
         list->count = 0;
         list->item = NULL;
         return NULL;
      }
   } else {
      list->item = realloc(list->item, list->count * list->itemSize);
      if (!list->item) {
         list->count = 0;
         list->item = NULL;
         return NULL;
      }
   }
   void *i = list->item + (list->count - 1) * list->itemSize;
   memcpy(i, item, list->itemSize);
   return i;
}

void *linsert(List *list, uint32_t index, void *item) {
   list->count++;
   if (list->count == 1) {
      list->item = malloc(list->itemSize);
      if (!list->item) {
         list->count = 0;
         list->item = NULL;
         return NULL;
      }
   } else {
      list->item = realloc(list->item, list->count * list->itemSize);
      if (!list->item) {
         list->count = 0;
         list->item = NULL;
         return NULL;
      }
   }
   if (index >= list->count) index = list->count - 1;
   uint32_t j;
   for (j=index; j<=list->count-1; j++)
      memcpy(list->item + (list->count - j + 1) * list->itemSize, list->item + (list->count - j) * list->itemSize, list->itemSize);
   void *i = list->item + index * list->itemSize;
   memcpy(i, item, list->itemSize);
   return i;
}

void lremove(List *list, uint32_t index) {
   if (!list) return;
   if (!list->count) return;
   list->count--;
   if (!list->count) {
      free(list->item);
      return;
   }
   if (list->count - index < 2) return;
   if (index >= list->count) index = list->count - 1;
   memcpy(list->item + index * list->itemSize, list->item + (index + 1) * list->itemSize, list->itemSize * (list->count - index + 1));
   list->item = realloc(list->item, list->count * list->itemSize);
}

void lremoveLast(List *list) {
   if (!list) return;
   if (!list->count) return;
   list->count--;
   if (!list->count) {
      free(list->item);
      return;
   }
   list->item = realloc(list->item, list->count * list->itemSize);
}

void *lget(List *list, uint32_t index) {
   if (!list) return NULL;
   if (index >= list->count) return NULL;
   return list->item + index * list->itemSize;
}

void *lset(List *list, uint32_t index, void *item) {
   if (!list) return NULL;
   if (index >= list->count) return NULL;
   void *i = list->item + index * list->itemSize;
   memcpy(i, item, list->itemSize);
   return i;
}

EDIT:
Wanted people to know I made some slight changes to the code since I first posted it.

• the 'lnew' function now takes an argument to create a list with a specific number of elements (before it just took the item size and returned an empty list)
• removed a 'printf' from the 'lremove' function that I accidentally left behind
• added 'lresize' function
• modified the laddc and lpushc macros to use lresize, making it a little faster than before
• added a 'lclear' function
• fixed 'ldestroy'

I also have another library I've written for command line argument parsing, but its sloppy and slow. I'll try to optimize it a bit and post the code.

[bluemoon]

This is what I called flat, auto sized array, and this is a few improvement/suggestions for you:
1. you may pre-allocate in chunks to avoid frequent allocations
2. you may break down the allocation to reduce stress from realloc (imagine you expand from 10000 ro 10001 elements)

This is what my array look like:

Code: Select all

template <class T>
class	libprefix_Array {
public:
	libprefix_Array();
	~ libprefix_Array (); // not suppose to be inherited, no virtual
	void	clear ();
	T*	get(int index);
	int	count() { return counter; }
protected:
	static const int kChunkSize = 16;
	int	item_node_count, item_node_allocated, counter;
	T**	item;
};
template <class T>
T* libprefix_Array<T>::get(int index) {
    int chunk = index / kChunkSize;
    if ( chunk >= item_node_allocated ) {
        // expand item pointer table
    }
    if ( item[chunk] == NULL ) {
        // allocate payload
    }
    return &item[chunk][index % kChunkSize];
}

And guess what, this is one of the class that I never used in any scenario, in all cases I used linked list, map (hash table), bi-directional map, or just boost.