db mix – postgres, sqlite, cassandra, aerospike & redis

SQLite

How to delete all tables from sqlite:

SELECT 'DROP TABLE ' || name || ';' FROM sqlite_master WHERE type = 'table';

Find duplicates by field “field_name”:

SELECT field_name, COUNT(field_name) AS cnt FROM some_table GROUP BY field_name HAVING(cnt > 1 ) FIXME - use cnt?

Find records changed in last 5 days:

SELECT * FROM some_table WHERE created_at >= NOW() - '5 day'::INTERVAL;

Get table definitions:

pragma table_info(mass_connections);

Export select query to csv:

.mode csv
.output result_of_query.csv
select * from my_table;
.output stdout 

Import data from csv into fresh new table:

.mode csv
.import /path/to/your/all_data.csv new_table

Postgres

How to show all tables with sizes within database

SELECT schema_name, relname, pg_size_pretty(table_size) AS size, table_size FROM ( 
SELECT pg_catalog.pg_namespace.nspname AS schema_name, relname, pg_relation_size(pg_catalog.pg_class.oid) AS table_size 
FROM pg_catalog.pg_class 
JOIN pg_catalog.pg_namespace ON relnamespace = pg_catalog.pg_namespace.oid) t 
WHERE schema_name NOT LIKE 'pg_%' ORDER BY table_size DESC;

Show average amount of records per table

SELECT schemaname,relname,n_live_tup FROM pg_stat_user_tables ORDER BY n_live_tup DESC;

How to create data-only dump:

pg_dump -U your_pg_user -h pg_ip_address -p pg_port -a --column-inserts db_name > file_name.sql
pg_dump -U your_pg_user -h pg_ip_address -p pg_port -a --column-inserts --table=table_name db_name > file_name.sql

Useful pg_dump flags:

  • – C adds the CREATE statements
  • – s dump schema only
  • – a dump schema & data
  • – D dump using inserts (to simplify uploading data from PG into another db engine)

How to restore data:

psql dbname < infile.sql

PG stop/start:

$(PG_HOME)/bin/pg_ctl -D /data stop -m immediate
$(PG_HOME)/bin/pg_ctl start -D /data -l logfile

Aerospike:

Get settings:

asinfo -v 'get-config:'

Set particular settings:

asinfo -v 'set-config:context=service;batch-max-requests=10000000'
asinfo -v 'set-config:context=network;timeout=10000000'
asinfo -v 'set-config:context=service;batch-index-threads==100'

How to register LUA-script:

set LUA_USERPATH '.'
register module 'your_script_name.lua'

more at http://www.aerospike.com/docs/guide/aggregation.html

How to build secondary index based on bin

CREATE INDEX _idx ON . (bin_name) NUMERIC

bin_name ~ field name

How to delete all records within set:
https://github.com/aerospike/delete-set

Redis:

How to register lua script:

redis-cli script load "$(cat /YOUR/PATH/script_name.lua)"

Cassandra

How to save results of query to the file:

cqlsh -e"select * from table_name where some_txt_attr='very tricky string';" > cassandra_file_query_result.txt

How to check node health:

nodetool status | awk '/^(U|D)(N|L|J|M)/{print $2}'

How to check compression ratio for particular table:

nodetool -h cassandra_ip cfhistograms some_keyspace some_table

How to check the dropped tasks count (at the bottom) at particular node:

watch -n 1 -d "nodetool tpstats"

How to do a “backup: of  cassandra:

nodetool snapshot

It will generate snapshot of data at /<your path from yaml file>/data/snapshot.

How to do a “restore” from snapshot:

  • restart the server
  • copy data from snapshot to the respective keyspace folder
  • delete content of every keyspace table at /<your path from yaml file>/data/
  • stop cassandra

Kafka

How to show groups:
For old consumers:

./bin/kafka-consumer-groups.sh --list --zookeeper 1.1.1.1:2181

For new consumers:

./bin/kafka-consumer-groups.sh --list --new-consumer --bootstrap-server 1.1.1.1:9092

How to show how many messages:

./bin/kafka-run-class.sh kafka.tools.GetOffsetShell --broker-list 1.1.1.1:9092 --topic --time -1 --offsets 1

How to show how many messages in ALL partitions:

./bin/kafka-run-class.sh kafka.tools.GetOffsetShell --broker-list 1.1.1.1:9092 --topic --time -1 --offsets 1 | awk -F ":" '{sum += $3} END {print sum}'

How to show topics:

./bin/kafka-topics.sh --zookeeper 1.1.1.1:2181 --list

How to show consumer’s lag:
For old consumers:

./bin/kafka-consumer-groups.sh --describe --zookeeper 1.1.1.1:2181 --describe --group | column -s , -t

For new consumers:

./bin/kafka-consumer-groups.sh --describe --new-consumer --bootstrap-server 1.1.1.1:9092 --describe --group | column -s, -t

How to run test consumer:

./bin/kafka-console-consumer.sh --from-beginning --new-consumer --bootstrap-server 1.1.1.1:9092 --topic

RabbitMQ

How to create exchange and queue:

rabbitmqadmin declare exchange --vhost=/ name=test123 type=direct
rabbitmqadmin declare queue --vhost=/ name=test_queue.123 durable=true
rabbitmqadmin --vhost="/" declare binding source="test123" destination_type="queue" destination="test_queue.123" routing_key="test_routing_key"

HDFS

Updating file access control:

hdfs -setfacl -m user:user_name:rwx /Some/Path
hadoop fs -chown user_name:group_name /Some/Path

Updating file access control recursive:

hdfs dfs -chown -R user_name:group_name /Some/Path

In case of following error:
>> java.io.IOException: Cannot obtain block length for LocatedBlock
Root cause: non-correctly closed files.  How to fix them:

hdfs fsck /Some/Path -files -openforwrite | grep OPENFORWRITE
hdfs debug recoverLease -path /Some/Path/corrupt.json -retries 5

7 sins of blatant ignorance and how to avoid them

…You produce software for some time. In most cases it even works.
Other developers tend to care about your opinion.
Damn, you even wear some fancy title like senior\principal\architect.
And here it is – suddenly you were offered to wear really posh title – CTO…

This is moment when real troubles get started.

I did mistakes by myself. I fought with others to prevent them from repeating of my past vicious moves.
And I wish list below appear every time I was about to make game changing decision.

 

A lot of challenges are awaiting for new CTO. How they can be avoided?

A lot of challenges are awaiting for new CTO. How they can be avoided?

1. Claim-to-be-universal tools suck. Always.

Do not make assumption based on bright hello-world example at promo web site.
In your case – it would be necessary to have some tricky functionality that this mega-framework does not support by design.

2. Be suspicious to any black-box like solution that promise all and everything at no price.

Never-ever expect that you are aware of the deep technical details.

In production, during important demo or pitch – impossible cases tend to jump out regardless of claims from probabilistic theory.
Listen to your team – they are your experts who (should) know about tiny nuances about setup, implementations and limitations.

3. Start simple. Focus on creating _working_ prototype fast.

Forget about speed, scalability, cluster, gpu-computing or “best practices” declared by yet another guru.
In 99.99999 percents of cases you do not need load balancing or advanced caching strategy.
You will iterate if it necessary.

4. Trendy stuff sucks.

Do not waste your time in fighting with bugs of another pre-alpha release of some looks like promising tool.

New database engine \ fresh from research lab language \ trendy paradigm – should be out of your list of consideration.

You need get stuff done. That’s it.
Good old bullet-proof solution are your choice.

Especially if you and team have experience of delivering some product with it.
Otherwise, year later you will realize that your repositories contains complicated workarounds and dirty hacks in desperate efforts to build initial DSL.

5. Listen to your team.

Measure & prototype. Be open-minded for their approach for solution.

Do not abandon idea only because you are not author of it. Encourage them for think out of box (even if it mean be contradicted to your opinion).

6. Books are your friends.

Inspire your team to learn new things and professional growth.  Make your habit to read every day – in long run it will make a huge difference.
Short articles from HN do not help you to build foundation of knowledge – it is just a tip of iceberg.
You never can be sure that you know enough – treat with suspicious any “undisputed” statements (and those who dare to make them).

7. Take it easy.

World of IT and software development is hilariously small.
You do not know whom you will be interviewed by next time.
Who will be contacted for additional reference.

All makes mistakes. Not everyone learn from them.

Avoid any illusions from QA department – in most cases software will not work as you expected in first version.

Positive vibes during stern fuck-ups is what makes our profession truly awesome and memorable.
Humor is your best way to deal with burnout, pressure and broken coffee machine.

Sprinkle usual working day of your team with few bits of laugh to remind everyone that programming is fun! 😀

Information retrieval, Search and recommendation engine:

Natural language processing:

https://class.coursera.org/nlp/lecture – Processing of texts written in ordinal languages
https://company.yandex.com/technologies/matrixnet.xml – search algorithm by Yandex
http://www.quora.com/What-is-the-search-algorithm-used-by-the-Google-search-engine-What-is-its-complexity

Information retrieval:

http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html – Introduction to Information Retrieval, Cambridge
http://stackoverflow.com/questions/25803267/retrieve-topic-word-array-document-topic-array-from-lda-gensim
http://stats.stackexchange.com/questions/89356/document-similarity-gensim
http://machinelearning.wustl.edu/mlpapers/paper_files/BleiNJ03.pdf – Latent Dirichlet Allocation (LDA)
http://radar.oreilly.com/2015/02/topic-models-past-present-and-future.html
http://en.wikipedia.org/wiki/Topic_model

Few examples of applications for the above:

http://graus.nu/tag/gensim/
https://github.com/sandinmyjoints/gensimtalk/blob/master/gensim_example.py
http://stackoverflow.com/questions/27032517/what-does-the-output-vector-of-a-word-in-word2vec-represent
https://github.com/sandinmyjoints/gensimtalk/blob/master/gensim_example.py
http://stats.stackexchange.com/questions/89356/document-similarity-gensim
http://stackoverflow.com/questions/6486738/clustering-using-latent-dirichlet-allocation-algo-in-gensim

Recommender systems:

https://www.coursera.org/learn/recommender-systems/ – video lectures – 101 for Recommendation System
http://www.ibm.com/developerworks/library/os-recommender1/ – introduction to approach and algorithms
http://www.cs.bme.hu/nagyadat/Recommender_systems_handbook.pdf – “Encyclopedia” of recommender systems
http://www.slideshare.net/xamat/kdd-2014-tutorial-the-recommender-problem-revisited – overview of recommendation algorithms
http://www.machinelearning.org/proceedings/icml2007/papers/407.pdf – Restricted Boltzmann Machines for Collaborative Filtering
http://wiki.hsr.ch/Datenbanken/files/Recommender_System_for_Geo_MSE_DB_Seminar_HS2013_Senn_Paper_final.pdf

Ready for use recommendation engine:

https://cloud.google.com/prediction/ – Google recommendation engine
https://mahout.apache.org – Apache recommendation and general purpose machine learning framework

Elastic Search – just a few useful snippets

Install head plugin or rely on oldschool curl utility in order to test your queries:

curl -XPOST 'http://ELASTICSEARCH_HOST:ELASTICSEARCH_PORT/INDEX_NAME/_search?pretty' -d 'PUT_PROPER_QUERY_HERE'

or

curl -XPOST 'http://ELASTICSEARCH_HOST:ELASTICSEARCH_PORT/INDEX_NAME/_search?pretty' -d@FILE_WITH_YOUR_JSON_REQUEST

Q: Show me example of query for complex, nested document?

A:

{ "query": 
    { "bool":
        { "must": [
            {"nested":
                 {"path": "document.sub_document",
                  "query": 
                       {"bool": 
                           {"must": [
                               { "match":
                                   { "document.sub_document.attribute": "PUT_YOUR_SEARCH_VALUE_HERE" }
                               }
                           ]}
                        }
                 }
           }]
        }
    }
}

NOTE: if what are you searching for in sub-sub-sub document – just add proper number of nested chains of “bool” “must” “nested” elements.

Q: I need full text search and aggregations (aka facets) by attribute in nested document.

A:

{ "query": 
    { "query_string": 
        { "query": "PUT_YOUR_SEARCH_STRING_HERE" }
    },
    "aggs":
        {"name_of_parent_aggregation":
            {"nested":
                {"path": "document.SUB_DOCUMENT"},
                    "aggs":
                    {"name_of_aggregation":
                        {"terms":
                            {"field": "document.SUB_DOCUMENT.ATTRIBUTE_NAME"}
                        }
                    }
            }
        }
}

Q: I need a full text search and aggregations by geo positions aka distance range.

NOTE: put proper values for “origin”, “field”, “ranges” fields.

{ "query":
    { "query_string":
        { "query": "PUT_YOUR_SEARCH_STRING_HERE" }
    },
    "aggs":
        {"name_of_parent_aggregation":
            {"nested":
                {"path": "document.SUB_DOCUMENT"},
                "aggs": 
                    {"name_of_aggregation":
                        {"geo_distance":
                            {"origin": "100500, 100500",
                            "field":"document.SUB_DOCUMENT.NAME_OF_YOUR_GEO_POINT_ATTRIBUTE",
                             "ranges": [{"to": 1000}, {"to": 3000, "from": 1000}, {"from": 3000}]
                             }
                         }
                    }
            }
        }
}

Q: I have fields in document that contains multiple words, I want them to be be aggregated not as separate single terms, but as a whole string.

A.1 put proper mapping for such field – “multi_field” or in most recent version of elasticsearch – just “fields”.


... document mapping, ...

YOUR_FIELD: {   "type": "string",
                "fields":
                {"raw":
                    { "type": "string", "index": "not_analyzed" }
                }
            }

... document mapping, ...

A.2 use such kind of queries for nested faceting:

{"query":
    {"query_string":
        {"query": "PUT_YOUR_SEARCH_STRING_HERE"}
    },
    "aggs":
        {"name_of_parent_aggregation": 
            {"nested":
                {"path": "document.SUB_DOCUMENT"},
                 "aggs":
                     {"name_of_aggregation":
                         {"terms":
                             {"field": "document.SUB_DOCUMENT.ATTRIBUTE_NAME.raw"}
                         }
                     }
            }
        }
}

Q: I want return all documents sorted by distance and my geo_point field in nested document.

NOTE: ATTRIBUTE_NAME should be mapped as geo_point at moment of writing – it can be done only via manually created mapping.

A:

{"query":
    {"match_all": {}},
    "sort": [
        {"_geo_distance": 
            {"document.SUB_DOCUMENT.ATTRIBUTE_NAME": 
                {"lat": 25,"lon": 55},
                 "order": "asc",
                 "unit": "km",
                 "distance_type": "plane"
            }
        }]
}

Q: I want to return aggregation only?

A:

{"size": 0,
    "aggs": {
        "name_of_1st_parent_aggregation": {
            "nested": {"path": "document.SUB_DOCUMENT"},
            "aggs": {
                "name_of_1st_aggregation": {
                    "terms": {
                        "field":"document.SUB_DOCUMENT.ATTRIBUTE_NAME"
        }}}},
        "name_of_2nd_parent_aggregation": {
            "nested": {"path": "document.SUB_DOCUMENT_1"},
            "aggs": {
                "name_of_2nd_aggregation": {
                    "terms": {
                        "field":"document.SUB_DOCUMENT_1.ATTRIBUTE_NAME_1.raw"
        }}}},
        "name_of_3rd_parent_aggregation": {
            "nested": {"path": "document.SUB_DOCUMENT_2"},
            "aggs": {
                "name_of_3rd_aggregation": {
                    "geo_distance":
                            {"origin": "100500, 100500",
                            "field":"document.SUB_DOCUMENT_2.NAME_OF_YOUR_GEO_POINT_ATTRIBUTE",
                             "ranges": [{"to": 1000}, {"to": 3000, "from": 1000}, {"from": 3000}]
                             }
                }
        }}
}

Q: I want autocomplete?

A-0. NOTE better to use n-gramm based approach

A-1. Prefix approach for autocomplete:

{
    "query":{"query_string" : {
        "default_field" : "field.name",
        "query" : "start_of_phrase*"
    }},   
    "fields":["field.name"]
}

A-2. by adding to document mapping additional suggest field:

...
"mappings" : {
    "document_type": {
        "properties":{
             "suggest" : {
                        "type" : "completion",
                        "index_analyzer" :"simple",
                        "search_analyzer" :"simple",
                        "payloads":"true"
                    },
....

When you add document for indexing you have to specify this additional information and use special endpoint _suggest for request suggestions:

{
    "suggest_name" : {
        "text" : "k",
        "completion" : {
            "field" : "suggest"
        }
    }
}

Q: I want filtering of a search result by nested attribute!

{
  "query": {
    "filtered": {
      "query": {
        "match_all": {}
      },
      "filter": {
        "or": [
          {
            "nested": {
              "path": "document.nested_attribute",
              "filter": {
                "bool": {
                  "must": [
                    {
                      "terms": {
                        "document.nested_attribute.attribute_value": [
                          1,
                          2
                        ]
                      }
                    }
                  ]
                }
              }
            }
          },
          {
            "nested": {
              "path": "document.nested_attribute_1",
              "filter": {
                "bool": {
                  "must": [
                    {
                      "terms": {
                        "document.nested_attribute_1.attribute_value": [
                          "some string value"
                        ]
                      }
                    }
                  ]
                }
              }
            }
          }
        ]
      }
    }
  }
}

Heterogeneous vector in c++ – overview of common approaches

So, you are wondering about heterogeneous vector in c++?
Maybe even dare to dream about any suitable substitution of such non-existent container?
In another word, you need a generic-like container that can store different datatypes.

If you just need a quick answer – stick with std::vector < boost::any> approach or read this,
If you need more technical-rich overview of purely templated solution – scroll down to links part,
If you are wondering about other options and don’t mind to dive in a world of bad English grammar and details about one of my recent task – read on.

heterogeneous container in c++

So, you want a heterogeneous container in c++…

First ask yourself – do you really need a heterogeneous vector?
If your answer is – yes, I have a bad news for you – in 99.9 percent it’s just consequences of messy design.
However, I am sure you are here for the sake of that one exceptional case: for example – your task is providing intermediate peace of software for interaction with some 3rd party old-fashion engine.

In my case – I was trying to implement convenient way of operating variable length list of parameters for OpenCL kernel wrapper.

If you are not familiar with mechanism of interaction of OpenCL code with C++, there are only one problem (sarcasm!) – it is too verbose. Off course there are numerous third party wrappers – http://streamcomputing.eu/knowledge/for-developers/opencl-wrappers/ but in situation where even NVidia drivers sometimes do not support all features from those-before-the-last standard,
I am afraid to think about cases when you have to deal with additional layer of external api.
Yeah, lets think about your own implementation because development of your own bugs is very entertaining and educational. It’s time consuming as well as terrible error-prone but you can narrow desired functional for your needs and be sure that all issues are made by you.

OpenCL kernels are compiled independently of host code, so you do not have any standard approaches for checking whether arguments provided to kernel have appropriate types and whether their amount corresponds to definition of kernel. It means that:
1) In case you are too lazy to somehow analyze every OpenCL kernels you can’t check how many arguments is necessary for particular kernel
2) You can’t check whether provided arguments have proper data type without any external parser

As a consequence, in general, my wrapper should be able to deal with variable length array of arbitrary any-type parameters.

(NOTE: Yeah, I’m familiar with undocumented c++ wrappers based on variadic templates, but it force you to follow their low-level nature by falling down from level of domain-specific objects to operating in terms of POD types.)

From that brief idea, I conclude that my goal was:

vector < gpu_arg > kernel_args;

where gpu_arg is a class that can encapsulate any data types – built-in as well as a user-defined.
Who have mentioned templates? How to create vector that can hold any templated parameter? (we discuss it a bit latter)

I approach – return to the ancient times
The most straightforward way – forget about C++ and rely on encapsulation of data into void* pointers with numerous C-way casting:

struct gpu_arg
{
  void* data;
  size_t size;
  // numerous helper methods here
  // NOTE: you have to add some kind of type_id to deal with data in proper way
};

I.e. kernel parser report that there should be following parameter set:

float, int, custom_class *

and when you start adding parameters it treat them as predefined types (with or without your own additional datatypes checks).

As an advantage of such idea – we can easily use it in run-time.
In addition, this solution is error-prone and can lead to cruel punishment during any code review.

II approach – std::tuple and variadic templates
On the other hand – in many cases when you are not keen to find a perfect silver bullet you may find helpful to simplify task. In order to check argument’s types you have to preprocess kernel, so you can form an expected parameter list. If you perform this operation during compilation of host-side code, you may use acquired parameter list to simplify code-generation task.
I started investigation of possible approaches and find out that the most obvious solution would be based on std::tuple:

// this C++11 container allows creation custom container like this:
std::tuple < int, int, bool, float *, unsigned short * > parameters_set;

or encapsulate it in a class with some syntax sugar for convenience:

template < typename ...T >
class arguments_set
{

    std::tuple<T...> data;
    template< size_t I >
    using data_type = typename std::tuple_element<I, decltype(data)>::type;

    /*
     *      variadic-based routine for initialize every element of tuple
     * */
   	template < std::size_t I = 0, typename TT >
	void
	init ( TT & arg )
	{
        std::get<I>( data ) = arg;
	};

	template < std::size_t I = 0, typename TT, typename ...Args>
	void
	init ( TT & arg, Args ... args )
	{
		init <I,TT> ( arg );
		init <I+1,Args...>( args ... );
	};

public:

    template<typename... Ts>
    arguments_set(Ts... args) {
       init <0,Ts...> ( args... );
    };

    template < std::size_t I = 0>
    constexpr
    auto get ( ) -> data_type<I>
    {
        return std::get<I>(data);
    }

};

Argh templates, well, who care about compiler’s effort to parse all this fluff?
Despite of convenience of variadic templates constructor, template metaprogramming is not easy to deal with during maintenance phase (as well as during developing).
On the other hand, it provides a desired result – strong type-checking combined with ability to generate variable length list of parameters.

So, solution was:
1) run pre-processor for OpenCL kernels in order to generate proper tuple for method invocation
2) compile the whole module

It is can be a solution in situation where you are not intend to run this mechanism in run-time.
(because it mean you have to dynamically extend templated class tuple objects)
Not my case.
Idea of pre-compiled kernels (PTX) sound great, but reality is sad – mess of drivers, hardware and vendor’s ambitions lead to incompatibility of generated binaries in general case. Not usable for me :(.
(But hope springs eternal – if you are lucky enough you can play with CL_CONTEXT_OFFLINE_DEVICES_AMD, http://clusterchimps.org/ocltools.php, http://www.browndeertechnology.com/coprthr.htm )

III approach – type erasure

Ok, let’s return to my preconditions once again:
1) I need type checking – template?
2) I need it in run-time – maybe some virtual stuff?!

What if I declare interface of argument as an abstract class and inherit it as a templated child with proper data fields

i.e.:

// pure abstract class
// in case of necessity can be further divided on pure interface\data-fields parts

class gpu_arg_base {
  /*
   *  interface part that depend on child's template parameter = a lot of virtual functions
   */
  /*
   *  common data fields with ordinary setters\getters methods
   */
}

template < typename T>
class gpu_arg : gpu_arg_base {
  /*
   * explicit override of interface with possible overloading
   */
  gpu_arg ( T* init_data);
  private:
    T *data; // NOTE: just a reference to data, no allocation\de-allocation!
};

It allow me to use them in following way:

class kernel_wrapper {
    vector <gpu_array_base*> kernel_params;
     /* some stuff here */
    public:
        // variadic template functions to deal with any number of parameters
        template < typename T>
	void
	add_kernel_args ( T * arg )
	{
		add_kernel_arg ( arg );
	};

	template <typename T, typename ...Args>
	void
	add_kernel_args( T * arg, Args ... args )
	{
		add_kernel_arg ( arg );
		add_kernel_args ( args ... );
	};

        // generating of proper function for particular type
        template<class T>
        void add_kernel_arg( T * host_data )
        {
	        gpu_arg_base* new_arg = new gpu_arg<T> ( host_data );
		kernel_params.push_back( new_arg );
        };

     /* interface part */
}

But be careful with this easy-looking approach – there are two main issues which can affect your mood and calmness.
First, read about differences between overriding and hiding of methods in inheritance hierarchy here or here. It is a great source of confusion, especially during investigation of fresh bug-reports.
Second, do not forget about “covariant return type” rules – http://aycchen.wordpress.com/2009/08/17/covariant-return-type-in-cpp/.
Great article about possible caveats and workaround can be found there:
http://nerdland.net/2009/06/covariant-templatized-virtual-copy-constructors/

After reviewing all solutions described above, you may find that you accept additional dependency in exchange for absence of disastrous side-effects of your implementation.
boost::any or boost::variant can be a proper choice.

PS. Actually, I suspect that using tuples and dark magic of template metaprogramming, you can save few ticks of processor’s time by abandoning inheritance and virtual table, but as usual during development we have to balance between concept of the perfect code and requirements of too fussy world.

LINKS:

Example of heterogeneous container ( deeply nested approach)
www.codeproject.com/Articles/23304/High-Performance-Heterogeneous-Container

Interesting practical example of tuple usage for ORM-like engine:
http://javol.wordpress.com/2009/08/06/type-safe-table-container-using-variadic-templates/
Some practical aspects of using tuples:
http://stackoverflow.com/questions/1198260/iterate-over-tuple
http://stackoverflow.com/questions/15411022/how-do-i-replace-a-tuple-element-at-compile-time
http://stackoverflow.com/questions/7858817/unpacking-a-tuple-to-call-a-matching-function-pointer

Using variadic templates to initialize tuples or other way round:
http://stackoverflow.com/questions/10014713/build-tuple-using-variadic-templates
http://stackoverflow.com/questions/21413045/variadic-variable-initialization-for-variadic-template
http://stackoverflow.com/questions/687490/how-do-i-expand-a-tuple-into-variadic-template-functions-arguments

Any class in c++:
http://codereview.stackexchange.com/questions/20058/a-c11-any-class
www.codeproject.com/Articles/11250/High-Performance-Dynamic-Typing-in-C-using-a-Repla

Illustration of variadic templates usages for generating C++11 variant class:
http://thenewcpp.wordpress.com/2012/02/15/variadic-templates-part-3-or-how-i-wrote-a-variant-class/

Hands-on experience with tuples:
http://yapb-soc.blogspot.ru/2012/12/fun-with-tuples.html
http://yapb-soc.blogspot.ru/2012/12/zipping-and-mapping-tuples.html

How to convert png pair of RGB and Depth frames into Pointcloud library PCD format

There are a lot of accessible dataset of RGB-D data:

http://vision.in.tum.de/data/datasets/rgbd-dataset
http://rgbd-dataset.cs.washington.edu/dataset.html
http://research.microsoft.com/en-us/projects/7-scenes/
http://www0.cs.ucl.ac.uk/staff/M.Firman/RGBDdatasets/

But usually it stored in PNG format and unfortunately Pointcloud library do not provide built-in function neither for treating it as a PointCloud nor for conversion it to PCD. For my experiments I need to test few points using data with ground truth estimation, thats why I have to code small utility for conversion purpose.

Due to sudden leisure I decided to share that peace of code – probably you can find it useful.

https://github.com/kruglov-dmitry/pnd2pcd_batch

From readme:

png2pcd_batch – simple command line utility to convert depth and rgb frames
from png format to PCL pointcloud.

There are 2 execution mode:
using file with association information i.e. containing rgb-depth png files correspondence
or just providing folders that contain depth and rgb frames ( not reccommended ).

In 1st case you should anyhow create associate file by yourself
(for further details check description of parse_freiburg function)
In 2nd case – correspondence strictly depends on file names, and you should check it twice,
to avoid situation when selected depth frame is not appropriate for rgb frame.
( add sorting to filenames vector using custom predicate )

All dataset related parameters are incapsulated in Intr structure ( intrinsics ).
There are: width, height, fx, fy, cx, cy, scale_factor.
Usually depth data is saved as unsigned short ( 16 bit ),
but in pcl::PointXYZ you have to re-scale it to float – metric measurment.

Appropriate intrinsics should be written to file cam_params.cfg otherwise
default values will be used ( which may lead to invalid output data ).

There are exist two opportunity for compiling:

using classical make:
edit WORK_DIR in Makefile to point in directory contained pcl-trunk & opencv
make
it produce more lightweighted version by avoiding linkage with unnecessary libraries

or using cmake:

mkdir build; cd build
cmake ..
make

NOTE 1: There are only two dependencies:
PCL and OpenCV.
NOTE 2: in case of builded-but-not-properly-installed OpenCV libraries you have to
manually create symlink to ipp lib:
sudo ln -s /path-to-opencv/3rdparty/ippicv/unpack/ippicv_lnx/lib/intel64/libippicv.a /usr/lib/libippicv.a

Note 3: it have built-in support for 16bit unsigned depth and 3-channel RGB data only, in case your data has another format you have to change code a bit
Note 4: do not forget to provide appropriate intrinsics for proper calculation of XYZ vertex

Templates in plain C

Templates in ANSI C – simple and convenient method for emulating c++ like templates in plain c. Sample project, which demonstrate this technics can be found at github.

So, it is our constraints:

  • ANSI C (no templates, inheritance, overloading, default params etc.)
  • set of almost the same user-defined structures (the common difference – is types of internal fields)
  • set of the functions, which operates on user-defined structures and provide a common interface used in the whole app

The most straightforward way to solve such task is just hard coded all necessary routine by hand:

/*		first type - type_int							*/
typedef struct type_int {
	int data;
} type_int;

type_int
make_type_int(int init_val) {
	type_int return_value;
	return_value.data = init_val;
	return return_value;
}

type_int
subtract_type_int (type_int A, type_int B) {
	return make_type_int ( A.data - B.data );
}

/*
 *		and a lot of different functions here
 */

 /*		second type - type_float						*/
typedef struct type_float {
	float data;
} type_float;

/*
 *		etc.
 */

This leads to a huge amount of copy-paste and increase chances of errors, especially in case of a large set of functions and vicious habit of the compiler to use implicit type conversion.
But what is most important – such way a bit annoying and leads to impression of bad “smell” of your own code.
So I decided to google around (all helpful link are located at the end of articles) and find out that indeed – the better way for emulating templates in plain C is exist!

Here is my how-to for generating declaration of structures and implementation of methods operating on them, which can be used further in the whole project.
The main trick here is to refresh the basis of C preprocessor and macros.

Firstly, lets define several helpful macros in file my_types.h:

#define CAT(X,Y) X##_##Y
#define TYPE_NAME(X,Y) CAT(X,Y)

They will be used to generate names of your structures and methods using simple rule – merge two params, using underscore as delimiter.
Using macros above lets create our simple structure in file my_type_templates.h:

typedef struct TYPE_NAME(TYPE, SUB_TYPE) {
	SUB_TYPE data;
} TYPE_NAME(TYPE, SUB_TYPE);

And add declaration and implementation of all necessary functions:

#ifndef INCLUDED_IN_IMPLEMENTATION_FILE

/* if this file is included in any header - just add there definition of interface */
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( SUB_TYPE init_value);

TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(subtract, TYPE_NAME(TYPE, SUB_TYPE) ) ( TYPE_NAME(TYPE, SUB_TYPE) A, TYPE_NAME(TYPE, SUB_TYPE) B);

/*
 *		long list of supported functions
 */

#else

/* if this file is included in implementation file, where defined flag INCLUDED_IN_IMPLEMENTATION_FILE than generate implementaion of functions
 */

/*	add implementain make_* functions 		*/
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( SUB_TYPE init_value ) {
	TYPE_NAME(TYPE, SUB_TYPE) return_value;

	return_value.data = init_value;

	return return_value;
}

/*	add implementain subtract_* functions 		*/
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(subtract, TYPE_NAME(TYPE, SUB_TYPE) ) ( TYPE_NAME(TYPE, SUB_TYPE) A, TYPE_NAME(TYPE, SUB_TYPE) B) {
	return TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( A.data - B.data );
}

#endif

NOTE: you should not use any global ifdefs in file my_type_templates.h, because we have to include it multiple times, for every new custom type. Preprocessor will generate actual struct’s names and appropriate functions for manipulating them.

After that lets specify all types, which should be used in our project in usual header file my_types.h. For every type, which we want to generate – just add define/undef command like this:

#define TYPE type
#define SUB_TYPE int
    #include <my_type_templates.h>
#undef TYPE
#undef SUB_TYPE

and add implementation of all functions to a source file – my_types.c – just define flag showing that it is actual implementation and include header file, containing all defined types:

#define INCLUDED_IN_IMPLEMENTATION_FILE
#include <my_types.h>

In your project you should use my_types.h header as usual – just include it in all dependent sources. We have used ifdef for implementation part of our template, so header doesn’t contain any functions implementation – therefore there is no ambiguity during linking and all necessary function would be compile only once – during compilation of file my_types.c.

So the final files should looks like following:

my_types.h

#ifndef MY_TYPES
#define MY_TYPES

#define CAT(X,Y) X##_##Y
#define TYPE_NAME(X,Y) CAT(X,Y)

#define TYPE type

#define SUB_TYPE int
	#include <my_type_templates.h>
#undef SUB_TYPE

#define SUB_TYPE float
	#include <my_type_templates.h>
#undef SUB_TYPE

#undef TYPE

#endif /* MY_TYPES */

my_types.c

/*
 *		Add all includes necessary for you implementations
 */
#define INCLUDED_IN_IMPLEMENTATION_FILE
#include <my_types.h>

That’s it. Using this trick you will achieve compile-time type-checks, decrease amount of boring hand-coded routine and avoid possible errors using another approach, based on void pointers and multiple run-time casts.

Additional resources:
http://arnold.uthar.net/index.php?n=Work.TemplatesC
http://stackoverflow.com/questions/1489932/c-preprocessor-and-concatenation
http://stackoverflow.com/questions/351733/can-you-write-object-oriented-code-in-c

Что почитать для проф развития программисту

Давно хотел как-то упорядочить свой список книг для внеклассного чтения для повышения проф-пригодности. Эти книжки для тех программистов, которые уже не совсем новички. Возможно уже и не совсем программисты – техлиды/архитекты. И хотят данную ситуацию усугубить.
Я из них прочитал еще не все 🙁
Но галочки уже расставляю 🙂

зы. Не думаю, что это нужно/интересно/полезно вот прям всем – это уже лично мой список отражающий текущие или прошлые профессиональные интересы. Я ж наверняка что-то позабыл включить, а что-то мне разонравится и я буду безжалостно это вычеркивать – так что в статье ожидаются правки 🙂

C++

  1. Язык программирования С++, Страуструп
  2. Эффективное использование C++. 55 верных способов улучшить структуру и код ваших программ, Мейерс Скотт
  3. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов, Мейерс Скотт
  4. C++: Библиотека программиста, Джефф Элджер
  5. Веревка достаточной длины, чтобы… выстрелить себе в ногу. Правила программирования на Си и Си++. Ален Голуб
  6. Стандарты программирования на С++. 101 правило и рекомедакция. Герб Саттер, Андрей Александреску
  7. C++. Практический подход к решению проблем программирования, Мэтью Уилсон
  8. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования, Андрей Александреску
  9. Advanced C++ Metaprogramming, Davide Di Gennaro
  10. Introduction to the Boost C++ Libraries, by Robert Demming

Алгоритмы

  1. Algorithms in a Nutshell, George T. Heineman, Gary Pollice, Stanley Selkow
  2. Алгоритмы на C++, Роберт Седжвик
  3. Алгоритмы. Построение и анализ, Томас Кормен
  4. Искусство программирования, Дональд Э. Кнут

Сети

  1. Эффективное программирование TCP-IP, Снейдер Й.
  2. UNIX. Разработка сетевых приложений,  У. Р. Стивенс

Функциональный подход к программированию

  1. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Peter Norvig
  2. Learn You Some Erlang for Great Good!: A Beginner’s Guide, Fred Hebert
  3. ERLANG Programming, Francesco Cesarini, Simon Thompson
  4. Purely Functional Data Structures, Chris Okasaki
  5. Learn You a Haskell for Great Good!: A Beginner’s Guide, Miran Lipovaca

Проектирование ООП программ

  1. Head First Object-Oriented Analysis and Design, Brett D. McLaughlin, Gary Pollice, Dave West
  2. Head First Design Patterns, Elisabeth Freeman, Eric Freeman, Bert Bates, Kathy Sierra, Elisabeth Robson
  3. Head First Software Development, Dan Pilone, Russ Miles
  4. Domain-Driven Design: Tackling Complexity in the Heart of Software, Eric Evans
  5. An Introduction to Object-Oriented Analysis and Design and Iterative Development, Craig Larman

Компьютерное зрение

  1. Computer Vision: Models, Learning, and Inference, Simon J. D. Prince
  2. Multiple View Geometry in Computer Vision Richard Hartley, Andrew Zisserman
  3. Computer Vision: A Modern Approach, David A. Forsyth
  4. Компьютерное зрение, Шапиро, Стокман

ОБЩАЯ МЕТОДОЛОГИЯ ПРОГРАММИРОВАНИЯ

  1. Чистый код. Создание, анализ и рефакторинг, Роберт Мартин
  2. Совершенный код, Стив Макконнелл
  3. 97 этюдов для архитекторов программных систем, Нил Форд, Майкл Найгард, Билл де Ора
  4. Защищённый код, Майкл Ховард, Дэвид Леблан
  5. Рефакторинг. Улучшение существующего кода, Мартин Фаулер
  6. Шаблоны корпоративных приложений, Мартин Фаулер
  7. Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions, Bobby Woolf, Gregor Hohpe
  8. How to Design Programs: An Introduction to Programming and Computing, http://htdp.org/, Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi
  9. Structure and Interpretation of Computer Programs (SICP), http://mitpress.mit.edu/sicp, Harold Abelson, Gerald Jay Sussman, Julie Sussman
  10. The Pragmatic Programmer: From Journeyman to Master, Andrew Hunt
  11. Writing Solid Code, Steve Maguire
  12. Hacker’s Delight, Henry S. Warren
  13. The Software Architect’s Profession: An Introduction, Marc Sewel
  14. 19 смертных грехов, угрожающих безопасности программ, Ховард М., Лебланк Д., Виега Д.
  15. Компиляторы: принципы, технологии и инструменты, “книга дракона”, Альфреда В. Ахо, Рави Сети, Джеффри Д. Ульмана,
  16. Паттерны проектирования, Гамма, Хелм, Джонсон, Влиссидес
  17. Test Driven Development: By Example, Kent Beck
  18. Code Craft: The Practice of Writing Excellent Code, Pete Goodliffe
  19. The Art of Multiprocessor Programming, Maurice Herlihy
  20. The Architecture of Open Source Applications, Amy Brown, Greg Wilson

VIM (emacs – 😛)

  1. Practical Vim: Edit Text at the Speed of Thought, Drew Neil
  2. Learning the vi and Vim Editors, Arnold Robbins, Elbert Hannah, Linda Lamb

Project Managment

  1. Искусство войны, Сунь-Цзы
  2. Мифический человеко-месяц, или Как создаются программные системы, Фредерик Брукс
  3. The Psychology of Computer Programming, Gerald M. Weinberg
  4. Extreme Programming Explained, Kent Beck
  5. Agile Software Development: The Cooperative Game, Alistar Cockburn
  6. Peopleware: Productive Projects and Teams, Tom DeMarco
  7. Adaptive Software Development: A Collaborative Approach to Managing Complex Systems, James A. Highsmith
  8. Software Craftsmanship: The New Imperative, Pete McBreen
  9. Dynamics of Software Development, Jim McCarthy
  10. Antipatterns: Managing Software Organizations and People, Colin J. Neill, Philip A. Laplante, Joanna F. DeFranco
  11. AntiPatterns in Project Management, William J. Brown
  12. Beyond Chaos: The Expert Edge in Managing Software Development, Larry L. Constantine
  13. The Manager Pool: Patterns for Radical Leadership (Software Patterns Series), by Don Sherwood Olson
  14. Death March, Edward Yourdon
  15. Leading a Software Development Team: A developer’s guide to successfully leading people, Richard Whitehead
  16. Head First PMP, Jennifer Greene, Andrew Stellman
  17. Agile Software Development, Principles, Patterns, and Practices, Robert C. Martin
  18. Цель. Процесс непрерывного совершенствования, Элияху М. Голдрат, Джефф Кокс
  19. Как пасти котов. Наставление для программистов, руководящих другими программистами, Дж. Ханк Рейнвотер

UX design

  1. A Project Guide to UX Design: For user experience designers in the field or in the making (2nd Edition) (Voices That Matter), Russ Unger, Carolyn Chandler

и, на посошок

Некоторые любопытные обсуждения литературы для проф развития:

http://stackoverflow.com/questions/1711/what-is-the-single-most-influential-book-every-programmer-should-read
http://habrahabr.ru/post/135897/
http://mrelusive.com/books/books.html – список книг для разработчика игр

Что почитать начинающему программисту

В связи с тем, что периодически меня спрашивают – что почитать зеленому новичку, для становления на скользкий путь программирования – я решил вот прям тут назвать те книжки, по которым когда-то начинал сам.И которые до сих пор поминаю добрым словом.

Будет актуально для linux/windows системных и прикладных разработчиков. Если вы прочитаете и сможете пользоваться этим знанием – 85% процентов вакансий уровня middle (ну и junior) – ваши.

1st programming bookЯ тоже перфекционист. Но даже мне кажутся изрядно раздутыми общедоступные списки книг для начинающих программистов. Причем некоторые книги в этих списках, новичкам, по моему мнению, просто противопоказаны. Ну нельзя подавляющему большинству нормальных людей путь в с++ начинать со Страуструпа. Можно сколько угодно ломать копья, обсуждая фундаментальные труды Кнута, но такое чтиво, особенно если университетский курс вышки подзабыт, быстро вгоняет в уныние, навевая мысли о проф. непригодности. К таким суровым упражнением будет милосерднее подходить спустя пару лет разминки в боевых условиях. Когда по граблям проторены тропы и начинает формироваться опасная иллюзия, что мол который год уже программирую – чем это меня тут еще удивить можно? Computer science?! Не, не слышал.

Мне кажется – вредным вываливать на человека, только-только ступившего на нелегкую стезю программирования бесконечный листинг вообще всех значимых произведений от признанных мастодонтов жанра отразивших свой опыт, свой взгляд на индустрию и т.п. Да, будет здорово, если вы будете держать в уме такой список и потихоньку, ставить галочки по мере прочтения. Но уверения, что без всего этого в профессии нечего делать – кажутся мне излишне снобистскими.

Да, программирование это наука. Да, программирование – это математика (в явном или не очень виде). И всему этому учиться не переучиться. Но не все же сразу. А вот начинать я бы предложил в таком порядке:

Язык C – основа основ:

Язык программирования C - Керниган, Ритчи

Язык программирования C – Брайан Керниган, Деннис Ритчи
(C Programming Language by Brian W. Kernighan, Dennis M. Ritchie )

SQL – ну куда сейчас без баз данных:

SQL - запросы для простых смертных. Хернандес, Вьескас

SQL – запросы для простых смертных. Практическое руководство по манипулированию данными в SQL Майкл Дж. Хернандес, Джон Л. Вьескас
(SQL Queries for Mere Mortals: A Hands-On Guide to Data Manipulation in SQL by John L. Viescas, Michael J. Hernandez)

C++ – противоречивый, не простой и всемогущий 🙂

C++ за 21 день, Либерти

Джон Либерти Освой самостоятельно C++ за 21 день – прекрасная вводная книга в мир ужасных крестов
(Teach Yourself C++ in 21 Days – Jesse Liberty, Bradley L. Jones)

Линуксы – ОС кроме Windows?

Операционная система UNIX Робачевский, Немнюгин, Стесик

Операционная система UNIX Андрей Робачевский, Сергей Немнюгин, Ольга Стесик

Эту книжку уже можно пометить звездочкой – как не шибко простую для начинающих, но содержащую сокровенные знания о том как что работает в системе – как для администраторов так и для системных программистов – строение исполняемых файлов, чем отличается поток от процесса, IPC, примитивы синхронизации. А если этого будет мало: обратите внимание на

У. Ричард Стивенс, Стивен А. Раго: “UNIX. Профессиональное программирование”
Рихтер Джеффри “Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows” (не смотря на то, что сейчас миром десктопных приложений правят C# и Java, именно в этих книгах детально изложена информация об особенностях программирования под конкретную ОС)

Функциональное программирование – это уже сильно опционально, для постепенной подготовки организма к просвещению и философскому подходу к программированию. (Они хоть и на английском зато с доходчивыми картинками и объяснениями концепций буквально “на пальцах”).

The Little Schemer - Daniel P. Friedman Matthias Felleisen

The Little Schemer – Daniel P. Friedman Matthias Felleisen

The Seasoned Schemer - Daniel P. Friedman Matthias Felleisen

The Seasoned Schemer – Daniel P. Friedman Matthias Felleisen

Land of Lisp, Conrad Barski

Land of Lisp: Learn to Program in Lisp, One Game at a Time! – Conrad Barski

GPU-оптимизация – прописные истины

Ядер много не бывает…

 

Современные GPU – это монструозные шустрые бестии, способные пережевывать гигабайты данных. Однако человек хитер и, как бы не росли вычислительные мощности, придумывает задачи все сложнее и сложнее, так что приходит момент когда с грустью приходиться констатировать – нужна оптимизацию 🙁

В данной статье описаны основные понятия, для того чтобы было легче ориентироваться в теории gpu-оптимизации и базовые правила, для того чтобы к этим понятиям, приходилось обращаться по-реже.

Причины по которой GPU эффективны для работы с большими объемами данных, требующих обработки:

  • у них большие возможности по параллельному исполнению задач (много-много процессоров)
  • высокая пропускная способность у памяти

Пропускная способность памяти (memory bandwidth) – это сколько информации – бит или гигабайт – может может быть передано за единицу времени секунду или процессорный такт.

Одна из задач оптимизации – задействовать по максимуму пропускную способность – увеличить показатели throughput (в идеале она должна быть равна memory bandwidth).

Для улучшения использования пропускной способности:

  • увеличить объем информации – использовать пропускной канал на полную (например каждый поток работает с флоат4)
  • уменьшать латентность – задержку между операциями

Задержка (latency) – промежуток времени между моментами, когда контролер запросил конкретную ячейку памяти и тем моментом, когда данные стали доступны процессору для выполнения инструкций. На саму задержку мы никак повлиять не можем – эти ограничения присутствуют на аппаратном уровне. Именно за счет этой задержки процессор может одновременно обслуживать несколько потоков – пока поток А запросил выделить ему памяти, поток Б может что-то посчитать, а поток С ждать пока к нему придут запрошенные данные.

Как снизить задержку (latency) если используется синхронизация:

  • уменьшить число потоков в блоке
  • увеличить число групп-блоков

Использование ресурсов GPU на полную – GPU Occupancy

В высоколобых разговорах об оптимизации часто мелькает термин – gpu occupancy или kernel occupancy – он отражает эффективность использования ресурсов-мощностей видеокарты. Отдельно отмечу – если вы даже и используете все ресурсы – это отнюдь не значит что вы используете их правильно.

Вычислительные мощности GPU – это сотни процессоров жадных до вычислений, при создании программы – ядра (kernel) – на плечи программиста ложиться бремя распределения нагрузки на них. Ошибка может привести к тому, что большая часть этих драгоценных ресурсов может бесцельно простаивать. Сейчас я объясню почему. Начать придется издалека.

Напомню, что варп (warp в терминологии NVidia, wavefront – в терминологии AMD) – набор потоков которые одновременно выполняют одну и туже функцию-кернел на процессоре. Потоки, объединенные программистом в блоки разбиваются на варпы планировщиком потоков (отдельно для каждого мультипроцессора) – пока один варп работает, второй ждет обработки запросов к памяти и т.д. Если какие-то из потоков варпа все еще выполняют вычисления, а другие уже сделали все что могли – имеет место быть неэффективное использование вычислительного ресурса – в народе именуемое простаивание мощностей.

Каждая точка синхронизации, каждое ветвление логики может породить такую ситуацию простоя.  Максимальная дивергенция (ветвление логики исполнения) зависит от размера варпа. Для GPU от NVidia – это 32, для AMD – 64.

Для того чтобы снизить простой мультипроцессора во время выполнения варпа:

  • минимизировать время ожидания барьеров
  • минимизировать расхождение логики выполнения в функции-кернеле

Для эффективного решения данной задачи имеет смысл разобраться – как же происходит формирование варпов (для случая с несколькими размерностями). На самом деле порядок простой – в первую очередь по X, потом по Y и, в последнюю очередь, Z.

ядро запускается с блоками размерностью 64x16, потоки разбиваются по варпам в порядке X, Y, Z - т.е. первые 64 элемента разбиваются на два варпа, потом вторые и т.д.

ядро запускается с блоками размерностью 64×16, потоки разбиваются по варпам в порядке X, Y, Z – т.е. первые 64 элемента разбиваются на два варпа, потом вторые и т.д.

Ядро запускается с блоками размерностью 16x64. В первый варп добавляются первые и вторые 16 элементов, во второй варп - третьи и четвертые и т.д.

Ядро запускается с блоками размерностью 16×64. В первый варп добавляются первые и вторые 16 элементов, во второй варп – третьи и четвертые и т.д.

более подробно про это можно почитать тут:
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#thread-hierarchy

Как снижать дивергенцию (помните – ветвление – не всегда причина критичной потери производительности)

  • когда у смежных потоков разные пути исполнения – много условий и переходов по ним – искать пути ре-структуризации
  • искать не сбалансированную загрузку потоков и решительно ее удалять (это когда у нас мало того что есть условия, дак еще из-за этих условиях первый поток всегда что-то вычисляет, а пятый в это условие не попадает и простаивает)

Как использовать ресурсы GPU по максимуму

Ресурсы GPU, к сожалению, тоже имеют свои ограничения. И, строго говоря, перед запуском функции-кернела имеет смысл определить лимиты и при распределении нагрузки эти лимиты учесть. Почему это важно?

У видеокарт есть ограничения на общее число потоков, которое может выполнять один мультипроцессор, максимальное число потоков в одном блоке, максимальное число варпов на одном процессоре, ограничения на различные виды памяти и т.п. Всю эту информацию можно запросить как программно, через соответствующее API так и предварительно с помощью утилит из SDK. (Модули deviceQuery для устройств NVidia, CLInfo – для видеокарт AMD).

Общая практика:

  • число блоков/рабочих групп потоков должно быть кратно количеству потоковых процессоров
  • размер блока/рабочей группы должен быть кратен размеру варпа

При этом следует учитывать что абсолютный минимум – 3-4 варпа/вейфронта крутятся одновременно на каждом процессоре, мудрые гайды советуют исходить из соображения – не меньше семи вейфронатов. При этом – не забывать ограничения по железу!

В голове все эти детали держать быстро надоедает, потому для расчет gpu-occupancy NVidia предложила неожиданный инструмент – эксельный(!) калькулятор набитый макросами. Туда можно ввести информацию по максимальному числу потоков для SM, число регистров и размер общей (shared) памяти доступных на потоковом процессоре, и используемые параметры запуска функций – а он выдает в процентах  эффективность использования ресурсов (и вы рвете на голове волосы осознавая что чтобы задействовать все ядра вам не хватает регистров).

сам калькулятор:
http://developer.download.nvidia.com/compute/cuda/CUDA_Occupancy_calculator.xls

информация по использованию:
http://docs.nvidia.com/cuda/cuda-c-best-practices-guide/#calculating-occupancy

GPU и операции с памятью

Видеокарты оптимизированы для 128-битных операций с памятью. Т.е. в идеале – каждая манипуляция с памятью, в идеале, должна изменять за раз 4 четырех-байтных значения. Основная неприятность для программиста заключается в том, что современные компиляторы для GPU не умеют оптимизировать такие вещи. Это приходится делать прямо в коде функции и, в среднем, приносит доли-процента по приросту производительности. Гораздо большее влияние на производительность имеет частота запросов к памяти.

Проблема обстоит в следующем – каждый запрос возвращает в ответ кусочек данных размером кратный 128 битам. А каждый поток использует лишь четверть его (в случае обычной четырех-байтовой переменной). Когда смежные потоки одновременно работают с данными расположенными последовательно в ячейках памяти – это снижает общее число обращений к памяти. Называется это явление – объединенные операции чтения и записи (coalesced access – good! both read and write) – и при верной организации кода (strided access to contiguous chunk of memory – bad!) может ощутимо улучшить производительность. При организации своего ядра – помните – смежный доступ – в пределах элементов одной строки памяти, работа с элементами столбца – это уже не так эффективно. Хотите больше деталей? мне понравилась вот эта pdf –  или гуглите на предмет “memory coalescing techniques“.

Лидирующие позиции в номинации “узкое место” занимает другая операция с памятью – копирование данных из памяти хоста в гпу. Копирование происходит не абы как, а из специально выделенной драйвером и системой области памяти: при запросе на копирование данных – система сначала копирует туда эти данные, а уже потом заливает их в GPU. Скорость транспортировки данных ограничена пропускной способностью шины PCI Express xN (где N число линий передачи данных) через которые современные видеокарты общаются с хостом.

Однако, лишнее копирование медленной памяти на хосте – это порою неоправданные издержки. Выход – использовать так называемую pinned memory – специальным образом помеченную область памяти, так что операционная система не имеет возможности выполнять с ней какие либо операции (например – выгрузить в свап/переместить по своему усмотрению и т.п.). Передача данных с хоста на видеокарту осуществляется без участия операционной системы – асинхронно, через DMA (direct memory access).

И, на последок, еще немного про память. Разделяемая память на мультипроцессоре обычно организована в виде банков памяти содержащих 32 битные слова – данные. Число банков по доброй традиции варьируется от одного поколения GPU к другому – 16/32 Если каждый поток обращается за данными в отдельный банк – все хорошо. Иначе получается несколько запросов на чтение/запись к одному банку и мы получаем – конфликт (shared memory bank conflict). Такие конфликтные обращения сериализуются и соответственно выполняются последовательно, а не параллельно. Если к одному банку обращаются все потоки – используется “широковещательный” ответ (broadcast) и конфликта нет. Существует несколько способов эффективно бороться с конфликтами доступа, мне понравилось описание основных методик по избавлению от конфликтов доступа к банкам памяти – тут.

Как сделать математические операции еще быстрее? Помнить что:

  • вычисления двойной точности – это высокая нагрузка операции с fp64 >> fp32
  • константы вида 3.13 в коде, по умолчанию, интерпретируется как fp64 если явно не указывать 3.14f
  • для оптимизации математики не лишним будет справиться в гайдах – а нет ли каких флажков у компилятора
  • производители включают в свои SDK функции, которые используют особенности устройств для достижения производительности (часто – в ущерб переносимости)

Для разработчиков CUDA имеет смысл обратить пристальное внимание на концепцию cuda stream,  позволяющих запускать сразу несколько функций-ядер на одному устройстве или совмещать асинхронное копирование данных с хоста на устройство во время выполнения функций. OpenCL, пока, такого функционала не предоставляет 🙁

Утиль для профилирования:

NVifia Visual Profiler
AMD CodeXL (бывший Amd APP Profiler)

Средства для дебугинга:
gDEBugger – http://www.gremedy.com/
CUDA-gdb – https://developer.nvidia.com/cuda-gdb

И отдельно хочу отметить функционал AMD APP KernelAnalyzer – статического анализатора кода (не требует наличия GPU в системе, умеет компилировать/разбирать собранные ядра для различных архитектур GPU от AMD). Сейчас входит в состав очередной системы для разработки все-в-одном – AMD CodeXL.
CUDA-MEMCHECK – анализатор от NVidia, призванный обеспечить функционал одноименного расширения для valgrind в мире CUDA-приложений.
http://multicore.doc.ic.ac.uk/tools/GPUVerify/ – интересная утилитка, анализирует ядра как CUDA так и OpenCL.

P. S. В качестве более пространного руководства по оптимизации, могу порекомендовать гуглить всевозможные best practices guide для OpenCL и CUDA.