Custom memcmp function

Question

I have written my own memcmp() function for learning purposes:

bool memcmp( byte* _bufA, byte* _bufB, uint n )
{
    while ( n > 4 )
    {
        if ( (int)*_bufA != (int)*_bufB )
            return false;
        _bufA += 4, _bufB += 4;
        n -= 4;;
    }
    while( --n )
    {
        if ( *_bufA != *_bufB )
            return false;
        ++_bufA, ++_bufB;
    }
    return true;
}

My thought process was that whenever the byte stream is greater than 4 bytes, I'd compare 4 bytes at a time instead of one. That means fewer iterations which would mean it would be a little more faster. And then just simply take care of the remaining 4 bytes or so in the second while statement.

Benchmarks:

• Standard memcmp function comparing 1024 bytes: 585 nanoseconds
• My memcmp function comparing 1024 bytes: 586 nanoseconds

It's pretty inconsistent but I figure it's still a pretty good function since it's 50/50 generally.

Answer 1

Correctness

Your function does not work correctly. In my experience, memory manipulating functions almost never work correctly as they are written the first time. (At least when I'm writing them.) If you need to go down into that rabbit hole, be sure to do so with an extensive set of unit-tests. In your case, you are lucky. You have two functions you can compare your results with:

• The existing memcmp function from the standard library and
• the naïve implementation of a for loop that compares one byte after the other.

When I'm writing optimized functions, I usually start with the naïve implementation. Then I write a comprehensive set of tests for it to make sure I got it right. (For the naïve version, this is usually easy.) Then I start optimizing the function and after each change, run the test suite again. Should one of my optimizations introduce a correctness bug, I'll notice.

Also be sure to run your unit tests trough Valgrind and compile test programs with sanitizers added. For GCC and Clang, all you have to do is pass the -fsanitize=WHAT switch where WHAT is one of address, memory or undefined. (memory is only supported by Clang yet.)

Cast the pointer, not the value

Have a look at this piece.

if ((int) *_bufA != (int) *_bufB)
  return false;

What does it do? It dereferences the pointers _bufA and _bufB which are of type byte * (which I assume is an alias for char *). Now, only after that, you cast the result (which is of type byte) to an int. In effect, you're only looking at each forth byte.

What you have to do instead is casting the pointer before dereferencing it.

if (*((int *) _bufA) != *((int *) _bufB))
  return false;

Watch out for off-by-one errors

Your second loop is off-by-one.

while (--n) { … }

If I call your function with n == 1, it'll never look at any byte. If chux decides to call it with n == 0, it will explode. The correct version would be to use post-decrement.

while (n--) { … }

On the other hand, your first loop could use

while (n >= 4) { … }

instead of

while (n > 4) { … }

even though this “bug” doesn't cause the function to produce a wrong answer, it is probably not what you've meant.

Do memory operations on unsigned types

While I don't think it would cause a problem in this particular case, using signed integer types can lead to all kinds of surprises. If you don't treat the values as numbers but as a bunch of bytes, stay with unsigned types.

Beware of undefined behavior

The C standard does not allow you to cast a pointer to another type (except char) to access the memory it points to. (This is a simplified explanation, search for “strict aliasing rules” for more information.) Therefore, your function invokes undefined behavior and this cannot be fixed other than by using the standard library functions.

That said, I think that this is a case where you can get pretty far with (extremely) carefully blundering the line of undefined behavior if you know what you are doing.

On many machines, memory must be aligned. That is, an object o of type T must have an address such that ((uintptr_t) &o) % alignof(T) == 0 where alignof(T) is called the alignment of type T. Unfortunately, alignof is not an operator in C (unlike in C++ since C++11). A safe estimate is to use the maximum of sizeof(T) and 8. Even on those machines where an unaligned memory access does not cause an exception, it might be slow.

Therefore, what you should do is check whether both pointers can be word-aligned by advancing both of them by the same number of bytes. If so, first do a short loop that aligns the buffers, then cast to a machine word type and compare the bulk. Finally, compare the remaining bytes with a byte-for-byte loop again.

-fsanitize=undefined can warn you about mis-aligned reads.

Portability

Don't make assumptions on sizeof(int)

Your function silently assumes that sizeof(int) == 4. This will not be true on all platforms. Instead of hard-coding such values, use sizeof(int). You can store it in a constant if repeating it seems too much typing.

Performance

Prefer longs over ints

In absence of any reason to do otherwise, unsigned long is your best bet to get a type that directly maps to a machine-word and will therefore give you optimal performance. Once I made this change to your code, I got significant speedup on my 64 bit machine from 2.9 GiB/s to 4.3 GiB/s!

Consider exiting early

If you anticipate that your function might regularly be called with aliasing pointers, it might be worthwhile to check for this.

if (p1 == p2)
  return true;

It doesn't cost much if the condition is false and will be an enormous short-cut if the pointers do alias.

Be sure to measure

Doing low-level optimization without measuring is a waste of time. You should compare your function with (at least) two alternatives:

• the naïve byte-for-byte approach and
• at least one highly optimized standard library implementation.

Before you do any optimization, be sure to compare those two approaches when compiled with all compiler optimizations turned on. If they don't differ much, you're probably done. Otherwise, deploy one optimization at a time and see how the performance of your implementation goes from “naïve” to “standard library”. If it goes below “naïve”, you're doing something wrong. If it goes above “standard library”, you did something awesome (or your function has a bug and doesn't do the same thing as the standard library version).

Writing good benchmarks is very hard. As a general rule, don't look at a single input but measure how the run-time scales with the input size. Also investigate the inevitable statistical errors your measurements will contain. I like to fit regressions to the data series and get a statistically more significant result from the fit parameters. Be sure to test large enough inputs so to reduce noise. Timings in the sub-millisecond range as you reported them are hardly significant.

I did this for your problem and got this result on my machine. Your version (with the fixes discussed above and using unsigned long) is not doing bad. Note, however, that the benchmark always tests the lucky case where the buffers can be aligned. I'll leave it as an exercise to you to test the more realistic case, too.

I'm dumping the code I've used to produce this data without any explanation here only so you can repeat the experiments on your hardware if you want to. It is a quick-and-dirty solution and I'm not particularly proud of the coding style but I believe that it tests accurately.

main.c:

#define _XOPEN_SOURCE 500  // random, srandom

#include <assert.h>        // assert
#include <math.h>          // isfinite, sqrt
#include <stdbool.h>       // bool, false, true
#include <stddef.h>        // size_t
#include <stdio.h>         // FILE, fopen, fclose, fprintf, snprintf, stderr
#include <stdlib.h>        // NULL, EXIT_{SUCCESS,ERROR}, malloc, free, random, srandom
#include <string.h>        // memcpy
#include <time.h>          // CLOCKS_PER_SEC, clock_t, clock

#include "memcmp.h"

// Tells the compiler that all previous changes to memory shall be visible.
#define CLOBBER_MEMORY()   __asm__ volatile ( "" : : : "memory" )

// Tells the compiler that the value of VAR shall be visible.
#define USE_VARIABLE(VAR)  __asm__ volatile ( "" : : "rm"(VAR) : )

// Type of the function to benchmark.
typedef bool (* memcmp_type)(const void *, const void *, size_t);

// Unsigned integer type that refers to a machine word.
typedef unsigned long word_type;

// Size of a machine word.
static const size_t word_size = sizeof(word_type);

// Global error message.
static const char * errmsg;

// Average value and statistical error of a statistical data sample.
typedef struct
{
  double average;  // average value (eg mean)
  double error;    // statistical error
} timing_result;

// Computes the square of a number.
static double
square(const double x)
{
  return x * x;
}

// Computes mean and standard deviation of the `n` data points in the array
// `datapoints`.  `n` must be at least 3.  The mean is stored at
// `resultptr->average` and the standard deviation at `resultptr->error`.
// Returns 0 on success.  On error a negative number is returned and `errmsg`
// is set.
static int
do_statistics(const double *const datapoints,
              const size_t n,
              timing_result *const resultptr)
{
  assert(n >= 3);
  double accu = 0.0;
  for (size_t i = 0; i < n; ++i)
    accu += datapoints[i];
  const double mean = accu / n;
  if (!isfinite(mean))
    {
      errmsg = "non-finite mean";
      return -1;
    }
  accu = 0.0;
  for (size_t i = 0; i < n; ++i)
    accu += square(datapoints[i] - mean);
  const double stdev = sqrt(accu / (n - 1));
  if (!isfinite(stdev))
    {
      errmsg = "non-finite standard deviation";
      return -1;
    }
  resultptr->average = mean;
  resultptr->error = stdev;
  return 0;
}

// Randomly maybe changes a single byte in the word pointed to by `wp`.
// Returns whether any byte was changed.
bool
maybe_change_byte(word_type *const wp)
{
  assert(wp != NULL);
  unsigned char bytes[word_size];
  const word_type before = *wp;
  memcpy(bytes, wp, word_size);
  const size_t index = random() % word_size;
  if ((random() % word_size) != 0)
    bytes[index] = (unsigned char) random();
  memcpy(wp, bytes, word_size);
  return (*wp != before);
}

// Runs a single benchmark for the function `funcptr` on an input of
// approximately `input_size` bytes.  The function will be called one more than
// `repetitions` times and the execution time of all but the first run will be
// collected statistically and stored in the record pointed to by `resultptr`.
// `repetitions` must be at least 3.  `buff1st` and `buff2nd` must be buffers
// of at least `input_size` bytes that can be accessed as arrays of
// `word_type`.  The buffers must not overlap.  They will be used internally as
// work-space.  On success, 0 is returned.  On error, a negative number is
// returned and `errmsg` is set.
static int
run_benchmark(const memcmp_type funcptr,
              const size_t input_size,
              const size_t repetitions,
              word_type *restrict const buff1st,
              word_type *restrict const buff2nd,
              timing_result *const resultptr)
{
  assert(funcptr != NULL);
  assert(repetitions >= 3);
  assert(buff1st != NULL);
  assert(buff2nd != NULL);
  assert(buff1st != buff2nd);
  assert(resultptr != NULL);
  const size_t words = input_size / word_size;
  const size_t bytes = words * word_size;
  double timings[repetitions + 1];
  for (size_t i = 0; i < words; ++i)
    {
      const word_type w = random();
      buff1st[i] = w;
      buff2nd[i] = w;
    }
  for (size_t i = 0; i <= repetitions; ++i)
    {
      const clock_t no_clock = (clock_t) -1;
      const bool expected = (words >= 2)
        ? !maybe_change_byte(buff2nd + words - 2)
        : true;
      const size_t skip = (words >= 1) ? (random() % word_size) : 0;
      CLOBBER_MEMORY();
      const clock_t t0 = clock();
      const int actual = funcptr((const char *) buff1st + skip,
                                 (const char *) buff2nd + skip,
                                 bytes - skip);
      USE_VARIABLE(actual);
      const clock_t t1 = clock();
      if (actual != expected)
        {
          errmsg = "function returned wrong result";
          goto label_catch;
        }
      if ((t0 == no_clock) || (t1 == no_clock))
        {
          errmsg = "cannot get CPU time";
          goto label_catch;
        }
      timings[i] = (double) (t1 - t0) / CLOCKS_PER_SEC;
      if (words >= 2)
        buff2nd[words - 2] = buff1st[words - 2];
    }
  if (do_statistics(timings + 1, repetitions, resultptr) < 0)
    goto label_catch;
  resultptr->error += 1.0 / CLOCKS_PER_SEC;  // systematic error
  goto label_finally;
 label_catch:
  assert(errmsg != NULL);
 label_finally:
  return (errmsg == NULL) ? 0 : -1;
}

// Runs all benchmarks and for randomly chosen input sizes and writes the
// results to text files named `timing_${tag}.dat` in the current working
// directory where ${tag} identifies the benchmarked function.  Progress
// information is printed to standard error output.  Returns 0 on success.  On
// error, a negative number is returned and `errmsg` is set.
static int
run_all_benchmarks()
{
  const size_t repetitions = 10;
  const size_t datapoints = 50;
  const size_t max_size = 99 * (1ULL << 20);  // \lessapprox 100 MiB
  const size_t candidates = 3;
  const memcmp_type cand_funcs[] = {memcmp_naive, memcmp_stdlib, memcmp_yamiez};
  const char *const cand_names[] = {"naive", "stdlib", "yamiez"};
  assert(candidates == sizeof(cand_funcs) / sizeof(cand_funcs[0]));
  assert(candidates == sizeof(cand_names) / sizeof(cand_names[0]));
  word_type *const buff1st = malloc(max_size);
  word_type *const buff2nd = malloc(max_size);
  if ((buff1st == NULL) || (buff2nd == NULL))
    {
      errmsg = "out of memory";
      goto label_catch_outer;
    }
  for (size_t candidx = 0; candidx < candidates; ++candidx)
    {
      FILE * fh = NULL;
      fprintf(stderr, "%-12s ", cand_names[candidx]);
      char filename[128];
      const int status = snprintf(filename, sizeof(filename), "timing_%s.dat",
                                  cand_names[candidx]);
      if ((status < 0) || ((size_t) status >= sizeof(filename)))
        {
          errmsg = "error in snprintf";
          goto label_catch_inner;
        }
      fh = fopen(filename, "w");
      if (fh == NULL)
        {
          errmsg = "cannot open output file";
          goto label_catch_inner;
        }
      if (fprintf(fh, "# %22s %24s %24s\n\n", "n", "average / s", "error / s") < 0)
        {
          errmsg = "I/O error";
          goto label_catch_inner;
        }
      for (size_t j = 0; j < datapoints; ++j)
        {
          size_t n = random() % max_size;
          timing_result result = {0.0, 0.0};
          if (run_benchmark(cand_funcs[candidx], n, repetitions, buff1st, buff2nd, &result) < 0)
            goto label_catch_inner;
          if (fprintf(fh, "%24zu %24.10e %24.10e\n", n, result.average, result.error) < 0)
            {
              errmsg = "I/O error";
              goto label_catch_inner;
            }
          fputc('.', stderr);
        }
      goto label_finally_inner;
    label_catch_inner:
      assert(errmsg != NULL);
    label_finally_inner:
      if (fh != NULL)
        {
          if (fclose(fh) != 0)
            errmsg = "error closing output file";
        }
      fprintf(stderr, "  %s\n", (errmsg != NULL) ? "failed" : "done");
      if (errmsg != NULL)
        goto label_finally_outer;
    }
  goto label_finally_outer;
 label_catch_outer:
  assert(errmsg != NULL);
 label_finally_outer:
  free(buff1st);
  free(buff2nd);
  return (errmsg != NULL) ? -1 : 0;
}

// Seeds the global pseudo random number generator via `srandom` and runs all
// benchmarks.  Progress information and error messages are printed to standard
// error output.  Benchmark results are written to text files in the current
// working directory.  Returns `EXIT_SUCCESS` on success or `EXIT_FAILURE` on
// error.
int
main()
{
  srandom((unsigned int) clock());
  if (run_all_benchmarks() < 0)
    {
      if (errmsg == NULL)
        errmsg = "unknown error";
      fprintf(stderr, "error: %s\n", errmsg);
      return EXIT_FAILURE;
    }
  return EXIT_SUCCESS;
}

memcmp.h:

#ifndef MEMCMP_H
#define MEMCMP_H

#include <stdbool.h>  // bool
#include <stddef.h>   // size_t

#ifdef __cplusplus
extern "C" {
#endif

bool
memcmp_stdlib(const void * s1, const void * s2, size_t n)
  __attribute__ ((hot));

bool
memcmp_naive(const void * s1, const void * s2, size_t n)
  __attribute__ ((hot));

bool
memcmp_yamiez(const void * s1, const void * s2, size_t n)
  __attribute__ ((hot));

#ifdef __cplusplus
}  // extern "C"
#endif

#endif  // #ifndef MEMCMP_H

memcmp_naive.c:

#include "memcmp.h"


bool
memcmp_naive(const void *const s1, const void *const s2, const size_t n)
{
  const unsigned char *const c1 = s1;
  const unsigned char *const c2 = s2;
  for (size_t i = 0; i < n; ++i)
    {
      if (c1[i] != c2[i])
        return false;
    }
  return true;
}

memcmp_stdlib.c:

#include "memcmp.h"

#include <string.h>  // memcmp


bool
memcmp_stdlib(const void *const s1, const void *const s2, const size_t n)
{
  return memcmp(s1, s2, n) == 0;
}

memcmp_yamiez.c:

#include "memcmp.h"

#include <stdint.h>  // uintptr_t


bool
memcmp_yamiez(const void *const s1, const void *const s2, size_t n)
{
  typedef unsigned char byte_type;
  typedef unsigned long word_type;
  const size_t word_size = sizeof(word_type);
  const size_t word_align = (word_size >= 8) ? word_size : 8;
  const uintptr_t align_mask = word_align - 1;
  const byte_type * buf1 = s1;
  const byte_type * buf2 = s2;
  const uintptr_t addr1 = (uintptr_t) s1;
  const uintptr_t addr2 = (uintptr_t) s2;
  if ((addr1 & align_mask) == (addr2 & align_mask))
    {
      const uintptr_t skip = word_align - (addr1 & align_mask);
      for (uintptr_t i = 0; i < skip; ++i)
        {
          if (*buf1++ != *buf2++)
            return false;
          --n;
        }
      const word_type * wbuf1 = (const word_type *) buf1;
      const word_type * wbuf2 = (const word_type *) buf2;
      while (n >= word_size)
        {
          if (*wbuf1++ != *wbuf2++)
            return false;
          n -= word_size;
        }
      buf1 = (const byte_type *) wbuf1;
      buf2 = (const byte_type *) wbuf2;
    }
  while (n--)
    {
      if (*buf1++ != *buf2++)
        return false;
    }
  return true;
}

Here is the Makefile I have used to compile the benchmarks.

CC = gcc
CPPFLAGS = -DNDEBUG
CFLAGS = -std=c11 -Wall -Wextra -Werror -pedantic -O3
LDFLAGS =
LIBS = -lm


compile: main

all: plot.png

plot.png: plot.gp timing_stdlib.dat timing_naive.dat timing_yamiez.dat
    gnuplot $<

timing_stdlib.dat timing_naive.dat timing_yamiez.dat: main
    ./$<

main: main.o memcmp_stdlib.o memcmp_yamiez.o memcmp_naive.o
    ${CC} -o $@ ${CFLAGS} $^ ${LDFLAGS} ${LIBS}

main.o: main.c memcmp.h
    ${CC} -c ${CPPFLAGS} ${CFLAGS} $<

memcmp_stdlib.o: memcmp_stdlib.c memcmp.h
    ${CC} -c ${CPPFLAGS} ${CFLAGS} $<

memcmp_yamiez.o: memcmp_yamiez.c memcmp.h
    ${CC} -c ${CPPFLAGS} ${CFLAGS} $<

memcmp_naive.o: memcmp_naive.c memcmp.h
    ${CC} -c ${CPPFLAGS} ${CFLAGS} $<

mostlyclean:
    rm -f fit.log *.o

clean: mostlyclean
    rm -f main *.dat plot.png

.PHONY: compile all mostlyclean clean

And here is the Gnuplot script plot.gp that produces the graphic shown above.

#! /usr/bin/gnuplot

## If you set the environment variable INTERACTIVE to a positive integer, the
## script will show the plot in an interactive Gnuplot window instead of
## writing to a file 'plot.png'.

interactive = 0 + system('echo "${INTERACTIVE-0}"')

if (!interactive) {
   set terminal png size 800,600
   set output 'plot.png'
}

set key top left
set xlabel 'size / MiB'
set ylabel 'time / ms'

set xrange [0 : *]
set yrange [0 : *]

set format y '%.0f'
set ytics add ('0' 0)

## Colors are taken from the Tango palette.
## See http://tango.freedesktop.org/Tango_Icon_Theme_Guidelines .

set style line 1 lt 2 lw 2.0 ps 1.0 linecolor '#3465a4'
set style line 2 lt 1 lw 2.0 ps 1.0 linecolor '#cc0000'
set style line 3 lt 3 lw 2.0 ps 1.0 linecolor '#73d216'

## Prefix constants

kilo = 1000.0
mebi = 1048576.0

## Converts a regression constant 'c1' in milliseconds per byte to a throughput
## in gibibytes per second.

c2gibps(c1) = kilo / (c1 * 1024)

## Computes the maximum of two numbers.

max(x, y) = (x < y) ? y : x

## Converts a size in bytes to a size in mebibytes.

b2mib(n) = n / mebi

## Converts a time in seconds to a time in milliseconds.

s2ms(t) = kilo * t

regression_naive(x)  = c1_naive  * x
regression_stdlib(x) = c1_stdlib * x
regression_yamiez(x) = c1_yamiez * x

fit regression_naive(x)                                                       \
    'timing_naive.dat'  using (b2mib($1)):(s2ms($2)):(s2ms($3))               \
    yerror via c1_naive

fit regression_stdlib(x)                                                      \
    'timing_stdlib.dat' using (b2mib($1)):(s2ms($2)):(s2ms($3))               \
    yerror via c1_stdlib

fit regression_yamiez(x)                                                      \
    'timing_yamiez.dat' using (b2mib($1)):(s2ms($2)):(s2ms($3))               \
    yerror via c1_yamiez

plot 'timing_naive.dat' using (b2mib($1)):(s2ms($2)):(s2ms($3))               \
         with yerror ls 1                                                     \
         title sprintf('%s (%.2f GiB/s)', "naive", c2gibps(c1_naive)),        \
     regression_naive(x) notitle ls 1,                                        \
     'timing_stdlib.dat' using (b2mib($1)):(s2ms($2)):(s2ms($3))              \
         with yerror ls 2                                                     \
         title sprintf('%s (%.2f GiB/s)', "stdlib", c2gibps(c1_stdlib)),      \
     regression_stdlib(x) ls 2 notitle,                                       \
     'timing_yamiez.dat' using (b2mib($1)):(s2ms($2)):(s2ms($3))              \
         with yerror ls 3                                                     \
         title sprintf('%s (%.2f GiB/s)', "yamiez", c2gibps(c1_yamiez)),      \
     regression_yamiez(x) notitle ls 3

if (interactive) {
   print "Hit RET to quit ..."
   pause -1
}

Learn from the giants

There has been massive interest in optimizing memory functions and standard libraries have evolved highly optimized versions. If you want to learn from them, have a look at their code. For example, look at the version in the GNU C library. If reading that code gives you a headache, you are in good companion.

Coding Style

Use the proper types

In C, a read-only buffer of arbitrary data should be passed as const void *. The size of a buffer should be passed as size_t.

Be const correct

Since your function only ever reads the data from the buffer it is passed, it should be declared const.

Don't use identifiers that begin with an underscore

Identifiers that begin with an underscore followed by an upper-case letter and identifiers containing two adjacent underscores are reserved for the implementation. I recognize that your variables don't match this pattern but _bufA still looks bogus. Just drop the underscore.

Avoid confusing notation

I find this hard to read.

if (*bufA != *bufB)
  return false;
++bufA, ++bufB;

How about the commonly used form?

if (*bufA++ != *bufB++)
  return false;

Less typing and easier to understand. In general, I'd avoid putting more than one statement on a single line and not chain multiple statements together with the comma operator.

Answer 2

The idea of comparing larger pieces of data is appealing, but requires great care to implement.

• The code assumes that the integer is 4 bytes wide. c doesn't guarantee it. A simple fix is to replace your 4s with sizeof(int).

• Alignment of buffers. If they happen to not be aligned on an int boundary anything may happen, from fault to slowdown to wrong results, depending on the underlying hardware architecture.

Answer 3

If speed is your goal then the next simple step would be to first use long long which in C99 or later is guaranteed to have at least 64bit.

The next step after this is using streaming intrinsics, for example _mm512_cmpeq_epu8_mask allows you to compare 64 bytes at once. However this is pretty much leaving the land of portability so depends on what exactly you want to do.

In general memcmp is probably by and large mostly memory bandwidth rather than CPU limited, so once the memory bandwidth is saturated comparing more stuff in parallel won't achieve much. For learning and educational purposes this might be a fun exercise though.

Answer 4

It's really hard to add anything to @5gon12eder's answer, but I'll try.

You tried to optimize the memory access by fetching 4 bytes at a time. That's a good approach. However be aware that the input buffers may be misaligned. If one of them starts at the DWORD (4-multiple) boundary and another one is one byte off (say, in case of memcmp(buf, buf+5) call), then accessing a misaligned 4-byte chunk may require two bus cycles per read. Of course a memory cache may help with minimizing that additional cost, but it's worth remembering the cost may appear.

Additionally, accessing misaligned data is strictly forbidden in some hardware architectures – if you try to read a 16-bit word from an odd address, or a 32-bit DWORD from an address not divisible by 4, an exception is raised in such device.

So to be fully portable and the fastest possible, your function should check the input pointers for the least common alignment factor and perform a loop with properly chosen chunk size (one- to four-, or even eight-byte, with appropriate type of char, int16, long, long long, depending on what types are available and what size they are).