Request to review code for best practices

[Ambush Commander]

A while back I posted a Fibonacci sequence calculator on this group,
and asked people to critique it. I received many helpful comments, and
made the program a lot better.

Now, I've converted it to use GMP so there's a bit of pointer work and
dynamic memory allocation going on. Can I, once again, have comments
on whether or not the code does "good practices", and where it could
be better? Thanks!

P.S. I am especially interested in comments for the fibonacci()
function; not so much for the processArgs() one.

----

/**
* Exercise #2.1
*
* Create a program that takes one argument and prints the
corresponding
* term from the Fibonacci series. There are also a number of extra
* features.
*/

#include <iostream>
#include <vector>

#include <boost/program_options.hpp>
#include <gmp.h>

/**
* Defines a whole number type (non-negative integer) that indexes the
* Fibonacci sequence. This type determines the nth term we can
calculate,
* though it has no bearing on the actual value of that term.
*/
typedef unsigned long WholeNumber;

/**
* Recursively calculates a term of the Fibonacci series.
* @param result Variable to write result to, no pointer necessary
* @param term Index of term in sequence
* @todo Convert code to use C++ GMP API
* @warning There is no way to free the internal cache
* @note I'm doing something very funky here: I'm using malloc in
order
to get the pointers to the arrays to persist... but GMP
also
has this sort of stuff going behind the scenes! So malloc
is being called twice! I don't know how to get around
this.
*/
void fibonacci(mpz_t result, WholeNumber term) {
static std::vector<mpz_t*> cache;
if (cache.empty()) {
// initialize cache with some (required) preloaded values
mpz_t *val0 = (mpz_t*) malloc(sizeof(mpz_t));
mpz_t *val1 = (mpz_t*) malloc(sizeof(mpz_t));
mpz_init(*val0);
cache.push_back(val0);
mpz_init(*val1);
mpz_set_ui(*val1, 1);
cache.push_back(val1);
}
if (cache.size() > term) {
// cache hit, return that value
mpz_init(result);
mpz_set(result, *cache[term]);
} else {
// cache miss, generate it
mpz_t val1, val2; // previous two values
fibonacci(val2, term - 2);
fibonacci(val1, term - 1);
mpz_t *valr = (mpz_t*) malloc(sizeof(mpz_t));
mpz_init(*valr);
mpz_add(*valr, val2, val1);
cache.push_back(valr);
mpz_init(result);
mpz_set(result, *valr);
}
}

/**
* Parses command line options, possibly returning messages
* @param vm Pointer to map to store argument information in
* @param argc Argument count
* @param argv Argument values
* @return Error code, or 1 to continue
*/
int processArgs(boost:rogram_options::variables_map *vm, int argc,
char *argv[]) {
using namespace boost:rogram_options;
using std::cout;

options_description desc("Options");
desc.add_options()
("help,h", "produce help message")
("list,l", value<WholeNumber>(), "list several Fibonnaci
numbers")
("term,t", value<WholeNumber>(), "print the nth term of the
series")
("nlsep,n", "format output with newlines, not commas")
;

positional_options_description p;
p.add("term", -1);

store(command_line_parser(argc,
argv).options(desc).positional(p).run(), *vm);
notify(*vm);

if (argc == 1 || vm->count("help")) {
cout << "\nFibonacci Numbers Generator\n By Edward Z. Yang\n
\n";
cout << "Usage: fibonacci [options] [term]\n";
cout << desc << "\n";
return 1;
}

return 0;
}

/**
* Main body
*/
int main(int argc, char *argv[]) {
using std::cout;
using std::string;

boost:rogram_options::variables_map vm;
int failed = processArgs(&vm, argc, argv);
if (failed) return failed;

if (vm.count("list")) {
std::string sep;
if (vm.count("nlsep")) {
sep = "\n";
} else {
sep = ", ";
}

WholeNumber max = vm["list"].as<WholeNumber>();
if (max == 0) max = 20; // set default value
mpz_t result;
for (WholeNumber i = 1; i < max; i++) {
fibonacci(result, i);
mpz_out_str(stdout, 10, result);
if (i != max - 1) cout << sep;
}
return 0;
}

// default behavior
WholeNumber term = vm["term"].as<WholeNumber>();
mpz_t result;
fibonacci(result, term);
mpz_out_str(stdout, 10, result);
return 0;

}

 

[Kai-Uwe Bux]

A while back I posted a Fibonacci sequence calculator on this group,
and asked people to critique it. I received many helpful comments, and
made the program a lot better.

Now, I've converted it to use GMP so there's a bit of pointer work and
dynamic memory allocation going on. Can I, once again, have comments
on whether or not the code does "good practices", and where it could
be better? Thanks!

P.S. I am especially interested in comments for the fibonacci()
function; not so much for the processArgs() one.

----

/**
* Exercise #2.1
*
* Create a program that takes one argument and prints the
corresponding
* term from the Fibonacci series. There are also a number of extra
* features.
*/

#include <iostream>
#include <vector>

#include <boost/program_options.hpp>
#include <gmp.h>

There is a c++ version: <gmpxx.h>. It proves a nice integer class mpz_class
that integrates nicely with operators and stuff. Moreover, it gets rid of
all the pointers.

/**
* Defines a whole number type (non-negative integer) that indexes the
* Fibonacci sequence. This type determines the nth term we can
calculate,
* though it has no bearing on the actual value of that term.
*/
typedef unsigned long WholeNumber;

/**
* Recursively calculates a term of the Fibonacci series.
* @param result Variable to write result to, no pointer necessary
* @param term Index of term in sequence
* @todo Convert code to use C++ GMP API
* @warning There is no way to free the internal cache
* @note I'm doing something very funky here: I'm using malloc in
order
to get the pointers to the arrays to persist... but GMP
also
has this sort of stuff going behind the scenes! So malloc
is being called twice! I don't know how to get around
this.
*/
void fibonacci(mpz_t result, WholeNumber term) {
static std::vector<mpz_t*> cache;
if (cache.empty()) {
// initialize cache with some (required) preloaded values
mpz_t *val0 = (mpz_t*) malloc(sizeof(mpz_t));
mpz_t *val1 = (mpz_t*) malloc(sizeof(mpz_t));
mpz_init(*val0);
cache.push_back(val0);
mpz_init(*val1);
mpz_set_ui(*val1, 1);
cache.push_back(val1);
}

Hm. The check is executed each time.

if (cache.size() > term) {
// cache hit, return that value
mpz_init(result);
mpz_set(result, *cache[term]);
} else {
// cache miss, generate it
mpz_t val1, val2; // previous two values
fibonacci(val2, term - 2);
fibonacci(val1, term - 1);
mpz_t *valr = (mpz_t*) malloc(sizeof(mpz_t));
mpz_init(*valr);
mpz_add(*valr, val2, val1);
cache.push_back(valr);
mpz_init(result);
mpz_set(result, *valr);
}

The above uses recursion. There is no need for that. You can replace the
whole thig with one

while ( n >= cache.size() ) {
compute next term
}



I would suggest to use a local class:


mpz_class const & fibonacci ( WholeNumber n ) {

class fib_cache {

std::vector< mpz_class > the_data;

public:

fib_cache ( void )
: the_data ()
{
the_data.push_back( mpz_class(0) );
the_data.push_back( mpz_class(1) );
}

mpz_class const & get ( std::vector< mpz_class >::size_type n ) {
while ( n >= the_data.size() ) {
the_data.push_back
( the_data[ the_data.size() - 1 ]
+
the_data[ the_data.size() - 2 ] );
}
assert( n < the_data.size() );
return ( the_data[n] );
}

};

static fib_cache dummy;
return ( dummy.get(n) );

}


Note how using mpz_class makes the code look like you would do it with
unsigned long.

[command line parsing snipped]


Best

Kai-Uwe Bux

 

[Ambush Commander]

There is a c++ version: <gmpxx.h>. It proves a nice integer class mpz_class
that integrates nicely with operators and stuff. Moreover, it gets rid of
all the pointers.

I was planning on changing that eventually. However, I wanted to get
my feet wet with a little C before using C++'s abstractions. I suppose
this would be the wrong list though!

Hm. The check is executed each time.

An alternative method would be to make the cache static throughout the
entire program and then have main() initialize it.

The above uses recursion. There is no need for that. You can replace the
whole thig with one

while ( n >= cache.size() ) {
compute next term
}

Point taken. I also realize that, given its current usage, I should
also be freeing up the memory used by all but the last two terms
(since the cache isn't being reused).

I would suggest to use a local class:

Does making the class local raise portability concerns?

I'm having difficulty understanding your code (because my syntax
knowledge of C++ is not very deep, and I only have a C Pocket
Reference book).

mpz_class const & fibonacci ( WholeNumber n ) {

The return type of this function is mpz_class, but what do the const
and & indicate?

class fib_cache {

std::vector< mpz_class > the_data;

public:

fib_cache ( void )
: the_data ()

Where is the return type for this function? Also, what does the second
line ": the data ()" do?

{
the_data.push_back( mpz_class(0) );
the_data.push_back( mpz_class(1) );
}

mpz_class const & get ( std::vector< mpz_class >::size_type n ) {

Once again, a const declaration. Not sure what this means...

while ( n >= the_data.size() ) {

Where did the "the_data" variable come from? Don't you need to use
this.the_variable?

the_data.push_back
( the_data[ the_data.size() - 1 ]
+
the_data[ the_data.size() - 2 ] );

Wouldn't evaluating the size() function this many times be
inefficient, or would allocating space for a counter variable be more
so?

}
assert( n < the_data.size() );

Is using assert useful? From where I come from, PHP, an assert()
function exists but is almost never used.

[snip]

Note how using mpz_class makes the code look like you would do it with
unsigned long.

Fair enough.

Thank you!

 

[Kai-Uwe Bux]

I was planning on changing that eventually. However, I wanted to get
my feet wet with a little C before using C++'s abstractions. I suppose
this would be the wrong list though!


An alternative method would be to make the cache static throughout the
entire program and then have main() initialize it.


Point taken. I also realize that, given its current usage, I should
also be freeing up the memory used by all but the last two terms
(since the cache isn't being reused).

No. Instead you should make the implementation reuse the stack. Otherwise
you have to recompute all values from the beginning each time fibonacci()
is called.

Does making the class local raise portability concerns?

No. Local classes are part of C++ and compilers are supposed to support
them. Anyway, you could always and easily move the class definition
outside.

I'm having difficulty understanding your code (because my syntax
knowledge of C++ is not very deep, and I only have a C Pocket
Reference book).


The return type of this function is mpz_class, but what do the const
and & indicate?

Read up on references and const references.

Anyway, that line actually is a mistake. It should be

mpz_class fibonacci ( WholeNumber n )

I was thinking, since all values of the fibonacci sequence are stored in the
vector, one could just return a reference into that vector. However, since
the vector may reallocate, that would not be safe.

Where is the return type for this function? Also, what does the second
line ": the data ()" do?

That function is a constructor. It does not have a return type.

The line

: the_data ()

is an initializer.

It appears that so far, you have studied the C-subset of C++. You should
learn about classes as soon as possible. They are the ++ in C++.

Once again, a const declaration. Not sure what this means...

It means that instead of an object only a reference to the object is
returned, i.e., a piece of information (realized by compiler magic) that
allows the the client code of the return value to access the actual
mpz_class object stored in the vector. To make sure that the client cannot
modify that stored value, the reference is qualified as const.

Where did the "the_data" variable come from? Don't you need to use
this.the_variable?

a) It would be this->the_data.
b) No, this-> is redundant most of the time.

the_data.push_back
( the_data[ the_data.size() - 1 ]
+
the_data[ the_data.size() - 2 ] );

Wouldn't evaluating the size() function this many times be
inefficient, or would allocating space for a counter variable be more
so?

I doubt that it would be inefficient. The size() method for std::vector<> is
encouraged to be constant time and very likely does nothing more than
returning a member variable of the vector object. The call is likely to be
inlined. It should not be more efficient to re-code the counting machinery
here. The vector will still increment its own size counter.

Is using assert useful? From where I come from, PHP, an assert()
function exists but is almost never used.

Absolutely! It checks whether my thinking process screwed up. In this case,
I just make sure that I got the condition in the while() right. This extra
layer of redundancy is a little safety net against the malfunctions of my
brain.

Also, I use asserts() regularly to enforce contracts. E.g., if I were to
implement std::vector, my operator[] would probably look like this:

value_type & operator[] ( size_type i ) {
assert( i < the_size );
return ( the_data );
}

The first line will make sure that client code fails if it tries to access
out of bounds.

(Note that if the client code needs an exception for this case, it has to
use the at() method.)

[snip]

Note how using mpz_class makes the code look like you would do it with
unsigned long.

Fair enough.

Best

Kai-Uwe Bux