Difference between 'new', 'new operator' and 'operator new' in C++

A question asked in a forum said:

Why does void* p = new (1024); gives me a compilation error while void* p = operator new (1024); works. What is the difference between new and "operator new"?

Lets go back to the beginning. Once upon a time there was this C language that used 'malloc' to allocate memory. Then when C++ came, a new way was defined of allocating memory by the use of 'new'. Its supposed to be much safter and better way but some software gurus may differ. Memory for 'new' is allocated from 'Free Store' and memory by 'malloc' is generated from 'heap'. The 'heap' and 'Free Store' may be the same area and is a compiler implementation detail.

The syntax for 'operator new' is:

void* new (std::size_t size);

All it does is allocate a memory of size specified

On the other hand, 'new' does 2 things:

1. It calls 'operator new'

2. It calls constructor for the type of object

In the above case since 1024 is not a type, it will fail in calling its constructor.

'new' is also referred to as 'keyword new' or 'new operator' to cause more confusion :)

Here is a small example to play with 'operator new' after the example you will realise that regardless of what is passed, it always allocates a 4 byte memory.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

int main()
{
 //void* p = new (1024);

 void* p = operator new (1024);

 //Lets test if we can do anything with the memory
  cout<<"p = "<<p<<endl;
 cout<<"sizeof(p) = "<<sizeof(p)<<endl;
 int *x = static_cast<int *>(p);
 cout<<"*x before = "<<*x<<endl;
 *x = 23456;
 cout<<"*x after = "<<*x<<endl;

 void* q = operator new (0);
 cout<<"\nq = "<<q<<endl;
 cout<<"sizeof(q) = "<<sizeof(q)<<endl;
 x = static_cast<int *>(q);
 cout<<"*x before = "<<*x<<endl;
 *x = 65432;
 cout<<"*x after = "<<*x<<endl;

 void* z = operator new ('a');
 cout<<"\nz = "<<z<<endl;
 cout<<"sizeof(z) = "<<sizeof(z)<<endl;
 x = static_cast<int *>(z);
 cout<<"*x before = "<<*x<<endl;
 *x = 11111;
 cout<<"*x after = "<<*x<<endl;

 return 0;
}

The output is as follows:

My knowledge in this area is quite limited so please feel free to improve on my explanation or correct it.

The switch statement in c++

The program that we create should be readable. To increase the readability of the program we should use tools that is simple to read and understand. When possible use switch statement rather than if else statement, as it can be more readable than if else statement. But switch statement has limitation. It can't replace if else completely but can be helpful at certain situation. It can't do everything thing that if else statement can do. For example, switch statement can take only int or char datatype in c++. The following programs will help you to understand the switch statement.

/* A simple c++ program example that demonstrate the use of switch statement in c++ by taking character input.*/

// Program 1


#include <iostream>

using namespace std;

int main ()
{
    char permit;

    cout << "Are you sure you want to quit? (y/n) : ";
    cin >> permit;

    switch (permit)
    {
        case 'y' :
            cout << "Hope to see you again!" << endl;
            break;
        case 'n' :
            cout << "Welcome back!" < < endl;
            break;
        default:
            cout << "What? I don't get it!" << endl;
    }

    return 0;
}

/* A c++ program example that demonstrate the use of switch statement in c++ by taking integer input. */

// Program 2

#include <iostream>
#include <iomanip>

using namespace std;

int main ()
{
    const int CHEESE_PIZZA = 11;
    const int SPINACH_PIZZA = 13;
    const int CHICKEN_PIZZA = 14;

    cout << " *********** MENU ***********" << endl;
    cout << setw (9) << "ITEM" << setw (20) << "PRICE" << endl;
    cout << " (1) Cheese Pizza" << setw (8) << "$"
            << CHEESE_PIZZA << endl;
    cout << " (2) Spinach Pizza" << setw (7) << "$"
            << SPINACH_PIZZA << endl;
    cout << " (3) Chicken Pizza" << setw (7) << "$"
            << CHICKEN_PIZZA << endl;
    cout << endl;

    cout << "What do you want? ";
    int option;
    cin >> option;

    cout << "How many? ";
    int quantity;
    cin >> quantity;

    int price;

    switch (option)
    {
        case 1:
            price = CHEESE_PIZZA;
            break;
        case 2:
            price = SPINACH_PIZZA;
            break;
        case 3:
            price = CHICKEN_PIZZA;
            break;
        default:
            cout << "Please select valid item from menu. " << endl;
            return 1;
    }

    int amount = price * quantity;
    cout << "Your Bill: $ " << amount << endl;

    return 0;
}

Explanation for the above program:

In the above program we take an integer value from the user which is stored in 'option' variable. We pass this value to switch statement. The switch statement has 3 cases: case 1, case 2 and case 3. The case 1: is similar to if (option == 1). This is the advantage of switch statement over if else statement. You don't need to type the name of variable again and again if you are doing selection operation on same variable. You just put the variable name on switch statement and then just specify the value after 'case'. One more thing to be noted is that it requires 'break' statement at the end of each 'case'. If you remove the break statement then it will jump to the case that follows it. Try it and check by yourself. The 'default' is same as else in if else statement.

C++ example of State Design Pattern

The State pattern allows an object to change its behavior when its internal state changes. This pattern can be observed in a vending machine. Vending machines have states based on the inventory, amount of currency deposited, the ability to make change, the item selected, etc. When currency is deposited and a selection is made, a vending machine will either deliver a product and no change, deliver a product and change, deliver no product due to insufficient currency on deposit, or deliver no product due to inventory depletion.

The frequency of use of State Pattern is Medium but is very useful and frequently used Telecoms Protocols implementation.

Example as follows:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//State is part of Behavioral Patterns 
//Behavioral Patterns deal with dynamic interactions among societies of classes and objects
//State allows an object to alter its behavior when its internal state changes. 
//     The object will appear to change its class  

//We will take an example Bank card where depending on the deposit the customers status changes


#include<iostream>
#include<string>
#include "main.h"


Account* State::GetAccount(void)
{
  return account_;
}
void State::SetAccount(Account* account)
{
  account_ = account;
}

double State::GetBalance(void)
{
  return balance_;
}

void State::SetBalance(double balance)
{
  balance_ = balance;
}

string State::GetStateName(void)
{
  return stateName_;
}

RedState::RedState(State* state)
{
  this->balance_ = state->GetBalance();
  this->account_ = state->GetAccount();
  Initialise();
}

void RedState::Deposit(double amount)
{
  balance_ += amount;
  StateChangeCheck();
}

void RedState::Withdraw(double amount)
{
  double newAmount = amount + serviceFee_;
  if(balance_ - newAmount < lowerLimit_)
    cout<<"No funds available for withdrawal!"<<endl;
  else
    balance_ -= newAmount;
}

void RedState::PayInterest()
{
  //No interest is paid
}

void RedState::StateChangeCheck()
{
  if (balance_ > upperLimit_)
  {
    account_->SetState(reinterpret_cast<State*>(new SilverState(this)));
    delete this;
    return;
  }
}

void RedState::Initialise()
{
  stateName_ = "Red";
  //Should come from a data source
  interest_ = 0.0;
  lowerLimit_ = -100.0;
  upperLimit_ = 0.0;
  serviceFee_ = 15.0;
}

SilverState::SilverState(State* state)
{
  this->balance_ = state->GetBalance();
  this->account_ = state->GetAccount();
  Initialise();
}

SilverState::SilverState(double balance, Account* account)
{
  this->balance_ = balance;
  this->account_ = account;
  Initialise();
}

void SilverState::Deposit(double amount)
{
  balance_ += amount;
  StateChangeCheck();
}

void SilverState::Withdraw(double amount)
{
  balance_ -= amount;
  StateChangeCheck();
}

void SilverState::PayInterest()
{
  balance_ = balance_ * interest_;
  StateChangeCheck();
}

void SilverState::StateChangeCheck()
{
  if (balance_ < lowerLimit_)
  {
    account_->SetState(reinterpret_cast<State*>(new RedState(this)));
    delete this;
    return;
  }
  else if (balance_ > upperLimit_)
  {
    account_->SetState(reinterpret_cast<State*>(new GoldState(this)));
    delete this;
    return;
  }
}

void SilverState::Initialise()
{
  stateName_ = "Silver";
  //Should come from a data source
  interest_ = 1.0;
  lowerLimit_ = 0.0;
  upperLimit_ = 1000.0;
}

GoldState::GoldState(State* state)
{
  this->balance_ = state->GetBalance();
  this->account_ = state->GetAccount();
  Initialise();
}

void GoldState::Deposit(double amount)
{
  balance_ += amount;
  StateChangeCheck();
}

void GoldState::Withdraw(double amount)
{
  balance_ -= amount;
  StateChangeCheck();
}

void GoldState::PayInterest()
{
  balance_ = balance_ * interest_;
  StateChangeCheck();
}

void GoldState::StateChangeCheck()
{
  if (balance_ < 0.0)
  {
    account_->SetState(reinterpret_cast<State*>(new RedState(this)));
    delete this;
    return;
  }
  else if (balance_ < lowerLimit_)
  {
    account_->SetState(reinterpret_cast<State*>(new SilverState(this)));
    delete this;
    return;
  }
  else if (balance_ > upperLimit_)
  {
    cout<<"Your account is too big now. Please consider using Swiss banks"<<endl;
  }
}

void GoldState::Initialise()
{
  stateName_ = "Gold";
  //Should come from a data source
  interest_ = 5.0;
  lowerLimit_ = 1000.0;
  upperLimit_ = 10000000.0;
}

Account::Account(string owner):owner_(owner)
{
  state_ = reinterpret_cast<State*>(new SilverState(0.0, this)); //default
}

Account::~Account()
{
  delete state_;
}

double Account::GetBalance(void)
{
  return state_->GetBalance();
}

void Account::Deposit(double amount)
{
  state_->Deposit(amount);
  cout<<"Deposited $"<<amount<<endl;
  cout<<"Balance   $"<<GetBalance()<<endl;
  cout<<"Status     "<<state_->GetStateName()<<endl;
  cout<<"\n";
}

void Account::Withdraw(double amount)
{
  state_->Withdraw(amount);
  cout<<"Withdrew  $"<<amount<<endl;
  cout<<"Balance   $"<<GetBalance()<<endl;
  cout<<"Status     "<<state_->GetStateName()<<endl;
  cout<<"\n";
}

void Account::PayInterest()
{
  state_->PayInterest();
  cout<<"Interest Paid --------"<<endl;
  cout<<"Balance   $"<<GetBalance()<<endl;
  cout<<"Status     "<<state_->GetStateName()<<endl;
  cout<<"\n";
}

void Account::SetState(State* state)
{
  state_ = state;
}

State* Account::GetState(void)
{
  return state_;
}


//The Main method
int main()
{
  Account* account = new Account("Dr. Who");
  account->Withdraw(10.00);
  account->Withdraw(30.00);
  account->Withdraw(70.00);
  account->Deposit(234.00);
  account->Deposit(5000.00);
  account->Withdraw(5200.00);
  account->Deposit(1500.00);
  account->Deposit(1.00);
  account->Withdraw(1200.00);

  delete account;

  return 0;
}

The output is as follows:

Further reading:

http://www.dofactory.com/Patterns/PatternState.aspx

http://www.patterndepot.com/put/8/state.pdf

http://sourcemaking.com/design_patterns/state

C++ example of Observer Design Pattern

Definition: Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.

Observers register themselves with the Subject as they are created. Whenever the Subject changes, it broadcasts to all registered Observers that it has changed.

The Observer defines a one-to-many relationship so that when one object changes state, the others are notified and updated automatically. Some auctions demonstrate this pattern. Each bidder possesses a numbered paddle that is used to indicate a bid. The auctioneer starts the bidding, and “observes” when a paddle is raised to accept the bid. The acceptance of the bid changes the bid price which is broadcast to all of the bidders in the form of a new bid.

Observer is a very popular pattern and its frequency of use is very high.

The following is an example of Observer Design Pattern:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Observer is part of Behavioral Patterns 
//Behavioral Patterns deal with dynamic interactions among societies of classes and objects
//An Observer is a way of notifying change to a number of classes.  

//We will take an example of Stock Price where, Observers can register to be told about
//the stock price change of a company

#include<iostream>
#include<string>
#include<list>

using namespace std;


//Forward Declaration
class Stock;

// The 'Observer' interface
class IInvestor
{
public:
  virtual void Update(Stock* stock){};
};

// The 'Subject' abstract class
class Stock
{
public:
  Stock(string symbol, double price) : symbol_(symbol), price_(price) { }
  void Attach(IInvestor* investor)
  {
    investors_.push_back(investor);
  }
  void Detach(IInvestor* investor)
  {
    investors_.remove(investor);
  }
  void Notify()
  {
    list<IInvestor*>::iterator it = investors_.begin();
    while(it != investors_.end())
    {
      (*it)->Update(this);
      ++it;
    }
  }
  double GetPrice(void)
  {
    return price_;
  }
  void SetPrice(double price)
  {
    price_ = price;
    Notify();
  }
  string GetSymbol(void)
  {
    return symbol_;
  }

private:
  string symbol_;
  double price_;
  list<IInvestor*> investors_;

  Stock();
};

// The 'ConcreteSubject' class
class Company : public Stock
{
public:
  Company(string name, string symbol, double price) : name_(name), Stock(symbol, price) {}
  string GetName(void)
  {
    return name_;
  }
private:
  string name_;
};

// The 'ConcreteObserver' class
class Investor : public IInvestor
{
public:
  Investor(string name) : name_(name){}
  void Update(Stock* stock)
  {
    cout<<"Notified "<<name_<<" about "<<(reinterpret_cast<Company*>(stock))->GetName() \
              <<" change to "<<stock->GetSymbol()<<stock->GetPrice()<<endl;
  }
private:
  string name_;
  Investor();
};

//The Main method
int main()
{
  Company* c1 = new Company("Google", "$", 123.0);
  cout<<"Created company Google with Stock Price 123.0\n"<<endl;

  Investor* i1 = new Investor("Billy");
  c1->Attach(i1);
  cout<<"Created investor Billy following Google\n"<<endl;

  c1->SetPrice(125.0);

  Investor* i2 = new Investor("Timmy");
  c1->Attach(i2);
  Investor* i3 = new Investor("Lenny");
  c1->Attach(i3);
  cout<<"\nCreated investor Timmy and Lenny following Google\n"<<endl;

  c1->SetPrice(145.0);

  c1->Detach(i1);
  c1->Detach(i3);
  cout<<"\nInvestor Billy and Lenny not interested in Google anymore\n"<<endl;

  c1->SetPrice(165.0);

  delete i1;
  delete i2;
  delete i3;
  delete c1;

  return 0;
}

The output is as follows:
Further Reading:

http://www.dofactory.com/Patterns/PatternObserver.aspx#_self2

http://sourcemaking.com/design_patterns/observer

http://www.patterndepot.com/put/8/observer.pdf

Number of bits to represent an arbitrary positive number X

Simple program to find the number of bits required to represent a positive number.

//This program is to find out the number of bits required to represent a positive integer
//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy

#include<iostream>
#include <cmath>

using namespace std;

unsigned int TraditionalApproach(const unsigned int& num)
{
  if(num)
  {
    return (int)floor(log((double)num)/log(2.0) + 1.0);
  }
  return 1;
}

unsigned int SimplifiedApproach(const unsigned int& num)
{
  if(num)
  {
    unsigned int tempNum = num;
    unsigned int numOfBits = 0;
    while(tempNum)
    {
      numOfBits++;
      tempNum >>= 1;
    }
    return numOfBits;
  }
  return 1;
}


int main()
{
  //Finding number of bits the traditional way
  cout<<"\n** Traditional Approach **\n";
  cout<<"The number of bits required to represent 0 = "<<TraditionalApproach(0)<<endl;
  cout<<"The number of bits required to represent 1 = "<<TraditionalApproach(1)<<endl;
  cout<<"The number of bits required to represent 15 = "<<TraditionalApproach(15)<<endl;
  cout<<"The number of bits required to represent 16 = "<<TraditionalApproach(16)<<endl;
  cout<<"The number of bits required to represent 75 = "<<TraditionalApproach(75)<<endl;
  cout<<"The number of bits required to represent 125 = "<<TraditionalApproach(125)<<endl;
  cout<<"The number of bits required to represent 130 = "<<TraditionalApproach(130)<<endl;

  cout<<"\n** Simplified Approach **\n";
  cout<<"The number of bits required to represent 0 = "<<SimplifiedApproach(0)<<endl;
  cout<<"The number of bits required to represent 1 = "<<SimplifiedApproach(1)<<endl;
  cout<<"The number of bits required to represent 15 = "<<SimplifiedApproach(15)<<endl;
  cout<<"The number of bits required to represent 16 = "<<SimplifiedApproach(16)<<endl;
  cout<<"The number of bits required to represent 75 = "<<SimplifiedApproach(75)<<endl;
  cout<<"The number of bits required to represent 125 = "<<SimplifiedApproach(125)<<endl;
  cout<<"The number of bits required to represent 130 = "<<SimplifiedApproach(130)<<endl;

  return 0;
}

The output is as follows:

Map Reduce and Stream Processing

Hadoop Map/Reduce model is very good in processing large amount of data in parallel. It provides a general partitioning mechanism (based on the key of the data) to distribute aggregation workload across different machines. Basically, map/reduce algorithm design is all about how to select the right key for the record at different stage of processing.

However, "time dimension" has a very different characteristic compared to other dimensional attributes of data, especially when real-time data processing is concerned. It presents a different set of challenges to the batch oriented, Map/Reduce model.

1. Real-time processing demands a very low latency of response, which means there isn't too much data accumulated at the "time" dimension for processing.
2. Data collected from multiple sources may not have all arrived at the point of aggregation.
3. In the standard model of Map/Reduce, the reduce phase cannot start until the map phase is completed. And all the intermediate data is persisted in the disk before download to the reducer. All these added to significant latency of the processing.
   

Here is a more detail description of this high latency characteristic of Hadoop.

Although Hadoop Map/Reduce is designed for batch-oriented work load, certain application, such as fraud detection, ad display, network monitoring requires real-time response for processing large amount of data, have started to looked at various way of tweaking Hadoop to fit in the more real-time processing environment. Here I try to look at some technique to perform low-latency parallel processing based on the Map/Reduce model.


General stream processing model

In this model, data are produced at various OLTP system, which update the transaction data store and also asynchronously send additional data for analytic processing. The analytic processing will write the output to a decision model, which will feed back information to the OLTP system for real-time decision making.

Notice the "asynchronous nature" of the analytic processing which is decoupled from the OLTP system, this way the OLTP system won't be slow down waiting for the completion of the analytic processing. Nevetheless, we still need to perform the analytic processing ASAP, otherwise the decision model will not be very useful if it doesn't reflect the current picture of the world. What latency is tolerable is application specific.

Micro-batch in Map/Reduce


One approach is to cut the data into small batches based on time window (e.g. every hour) and submit the data collected in each batch to the Map Reduce job. Staging mechanism is needed such that the OLTP application can continue independent of the analytic processing. A job scheduler is used to regulate the producer and consumer so each of them can proceed independently.

Continuous Map/Reduce

Here lets imagine some possible modification of the Map/Reduce execution model to cater for real-time stream processing. I am not trying to worry about the backward compatibility of Hadoop which is the approach that Hadoop online prototype (HOP) is taking.

Long running
The first modification is to make the mapper and reducer long-running. Therefore, we cannot wait for the end of the map phase before starting the reduce phase as the map phase never ends. This implies the mapper push the data to the reducer once it complete its processing and let the reducer to sort the data. A downside of this approach is that it offers no opportunity to run the combine() function on the map side to reduce the bandwidth utilization. It also shift more workload to the reducer which now needs to do the sorting.

Notice there is a tradeoff between latency and optimization. Optimization requires more data to be accumulated at the source (ie: the Mapper) so local consolidation (ie: combine) can be performed. Unfortunately, low latency requires the data to be sent ASAP so not much accumulation can be done.

HOP suggest an adaptive flow control mechanism such that data is pushed out to reducer ASAP until the reducer is overloaded and push back (using some sort of flow control protocol). Then the mapper will buffer the processed message and perform combine() before it send to the reducer. This approach automatically shift back and forth the aggregation workload between the reducer and the mapper.

Time Window: Slice and Range
This is a "time slice" concept and a "time range" concept. "Slice" defines a time window where result is accumulated before the reduce processing is executed. This is also the minimum amount of data that the mapper should accumulate before sending to the reducer.

"Range" defines the time window where results are aggregated. It can be a landmark window where it has a well-defined starting point, or a jumping window (consider a moving landmark scenario). It can also be a sliding window where is a fixed size window from the current time is aggregated.

After receiving a specific time slice from every mapper, the reducer can start the aggregation processing and combine the result with the previous aggregation result. Slice can be dynamically adjusted based on the amount of data sent from the mapper.

Incremental processing
Notice that the reducer need to compute the aggregated slice value after receive all records of the same slice from all mappers. After that it calls the user-defined merge() function to merge the slice value with the range value. In case the range need to be refreshed (e.g. reaching a jumping window boundary), the init() functin will be called to get a refreshed range value. If the range value need to be updated (when certain slice value falls outside a sliding range), the unmerge() function will be invoked.

Here is an example of how we keep tracked of the average hit rate (ie: total hits per hour) within a 24 hour sliding window with update happens per hour (ie: an one-hour slice).

# Call at each hit record
map(k1, hitRecord) {
   site = hitRecord.site
   # lookup the slice of the particular key
   slice = lookupSlice(site)
   if (slice.time - now > 60.minutes) {
       # Notify reducer whole slice of site is sent
       advance(site, slice)
        slice = lookupSlice(site)
    }
   emitIntermediate(site, slice, 1)
}

combine(site, slice, countList) {
   hitCount = 0
   for count in countList {
       hitCount += count
   }
   # Send the message to the downstream node
   emitIntermediate(site, slice, hitCount)
}

# Called when reducer receive full slice from all mappers
reduce(site, slice, countList) {
   hitCount = 0
   for count in countList {
       hitCount += count
   }
   sv = SliceValue.new
   sv.hitCount = hitCount
   return sv
}

# Called at each jumping window boundary
init(slice) {
   rangeValue = RangeValue.new
   rangeValue.hitCount = 0
   return rangeValue
}

# Called after each reduce()
merge(rangeValue, slice, sliceValue) {
   rangeValue.hitCount += sliceValue.hitCount
}

# Called when a slice fall out the sliding window
unmerge(rangeValue, slice, sliceValue) {
   rangeValue.hitCount -= sliceValue.hitCount
}

Memory Management with 'new'

Sometimes it is useful to take memory management in our control to make sure we have the right amount of memory already reserved in advance. This could be to speed up memory allocation/deallocation or for debugging purpose where contiguous memory allocation can speed up debugging or for variety of reasons.

The following example shows one way in which memory can be reserved in a chunk for the program.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include<iostream>

using namespace std;

class Class
{
public:
  int x;
  char y;
  bool z;
};

int main()
{
  unsigned char tempBuf[100];
  cout<<"Pointer for tempBuf = " << &tempBuf << endl;

  Class* c = new (tempBuf) Class;
  cout<<"Pointer for c = " << c << endl;

  return 0;
}

The output is as follows: