跳至主要内容

Implement isdigit

It is seems very easy to implement c library function isdigit, but for a library code, performance is very important. So we will try to implement it and make it faster.

Function

So, first we make it right.
int isdigit(char c) {
    return c >= '0' && c <= '9';
}

Improvements

One – Macro

When it comes to performance for c code, macro can always be tried.
#define isdigit(c) c >= '0' && c <= '9'

Two – Table

Upper version use two comparison and one logical operation, but we can do better with more space:
#define isdigit(c) table[c]
This works and faster, but somewhat wasteful. We need only one bit to represent true or false, but we use a int.
So what to do?
There are many similar functions like isalpha(), isupper ... in c header file, so we can combine them into one int and get result by table[c]&SOME_BIT, which is what source do.
Source code of ctype.h:
#  define _ISbit(bit)   (1 << (bit))

// mask of table
enum
{
  _ISupper = _ISbit (0),    /* UPPERCASE.  */
  _ISlower = _ISbit (1),    /* lowercase.  */
  _ISalpha = _ISbit (2),    /* Alphabetic.  */
  _ISdigit = _ISbit (3),    /* Numeric.  */
  _ISxdigit = _ISbit (4),   /* Hexadecimal numeric.  */
  _ISspace = _ISbit (5),    /* Whitespace.  */
  _ISprint = _ISbit (6),    /* Printing.  */
  _ISgraph = _ISbit (7),    /* Graphical.  */
  _ISblank = _ISbit (8),    /* Blank (usually SPC and TAB).  */
  _IScntrl = _ISbit (9),    /* Control character.  */
  _ISpunct = _ISbit (10),   /* Punctuation.  */
  _ISalnum = _ISbit (11)    /* Alphanumeric.  */
};

// __ctype_b_loc is the table with result
# define __isctype(c, type) \
  ((*__ctype_b_loc ())[(int) (c)] & 
      (unsigned short int) type)

# define isdigit(c) __isctype((c), _ISdigit)

Conclusion

When we deal with char/byte and require very fast implementation, use a table with result pre-computed is a good solution.
An example of this trick : How to reverse a byte’s bit as fast as possible? For example, convert ‘00010001’ to ‘10001000’.
Written with StackEdit.
标签：

评论

发表评论

此博客中的热门博文

Spring Boot: Customize Environment

Spring Boot: Customize Environment Environment variable is a very commonly used feature in daily programming: used in init script used in startup configuration used by logging etc In Spring Boot, all environment variables are a part of properties in Spring context and managed by Environment abstraction. Because Spring Boot can handle the parse of configuration files, when we want to implement a project which uses yml file as a separate config file, we choose the Spring Boot. The following is the problems we met when we implementing the parse of yml file and it is recorded for future reader. Bind to Class Property values can be injected directly into your beans using the @Value annotation, accessed via Spring’s Environment abstraction or bound to structured objects via @ConfigurationProperties. As the document says, there exists three ways to access properties in *.properties or *.yml : @Value : access single value Environment : can access multi...
5 条评论
阅读全文

LevelDB Source Reading (1): Structure

LevelDB Source Reading (1): Structure LevelDB “is an open source on-disk key-value store.” After I read some documents, I have some basic understanding of LevelDB. So I come up with some questions about structure of LevelDB to answer when reading the source code. Structure Log File: repair/recover db A log file (*.log) stores a sequence of recent updates. Each update is appended to the current log file. The log file contents are a sequence of 32KB blocks. The only exception is that the tail of the file may contain a partial block. Block format: Each block consists of a sequence of records: block := record* trailer? record := checksum: uint32 // crc32c of type and data[] ; little-endian length: uint16 // little-endian type: uint8 // One of FULL, FIRST, MIDDLE, LAST data: uint8[length] // data is LengthPrefixedSlice with type from batch data definition in Block : data: also named `writeBatch` in levelDB // WriteBatch header has an 8-byte ...
发表评论
阅读全文

LevelDB Source Reading (3): Compaction

LevelDB Source Reading (3): Compaction In the last blog that analyzes read/write process of Leveldb, we can see writing only happens to log file and memory table, then it relies on the compaction process to move the new updates into persistent sorted table for future use. So the compaction is a crucial part for the design, and we will dive into it in this blog. Compaction LevelDB compacts its underlying storage data in the background to improve read performance. The upper sentence is cited from the document of Leveldb , and we will see how it is implemented via code review. Background compaction // db_impl.cc void DBImpl :: MaybeScheduleCompaction ( ) { // use background thread to run compaction env_ - > Schedule ( & DBImpl :: BGWork , this ) ; } Two main aspects // arrange background compaction when Get, Open, Write void DBImpl :: BackgroundCompaction ( ) { // compact memtable CompactMemTable ( ) ; // compact ...
发表评论
阅读全文