No BSD License  

Highlights from
Finding the Similar Entries: A Quantitative Approach based on CPU Runtime Behavior

image thumbnail

Finding the Similar Entries: A Quantitative Approach based on CPU Runtime Behavior

by

 

08 Apr 2009 (Updated )

Entry to Matlab contest Spring 2009

compute_clam_sig(d, allLineList, entry_id);
%-------------------------------------------------------
% Filename:	compute_clam_sig.m
% Author:	C Jethro Lam, jethrolam@gmail.com
% Date:		4/4/2009
%
% Purpose:	Compute the clam signature of an entry
%
%-------------------------------------------------------
function [per_line_cpu_runtime clam_sig] = compute_clam_sig(d, allLineList, entry_id);     

if d(entry_id).passed
  % Extract the actual code of the entry from struct
  code_cell = allLineList(d(entry_id).lines);
 
  % Local variable
  num_lines = size(code_cell, 2);

  % Construct commands to be appended to code_cell
  append_cell	= cell(1, num_lines);
  for line_index = 1:num_lines
    % Convert into string
    line_string = sprintf('%s', code_cell{line_index});

    % Check if the line contain the keyword variables 'runtime_info', 'tic' or 'toc'; if yes, append with '_zxcvb'  
    kw_index = strfind(line_string,'runtime_info');
    if ~isempty(kw_index)
      code_cell{line_index} = [line_string(1:(kw_index-1)) 'runtime_zxcvb' line_string((kw_index+3):end)];
    end 
    kw_index = strfind(line_string,'tic');
    if ~isempty(kw_index)
      code_cell{line_index} = [line_string(1:(kw_index-1)) 'tic_zxcvb' line_string((kw_index+3):end)];
    end 
    kw_index = strfind(line_string,'toc');
    if ~isempty(kw_index)
      code_cell{line_index} = [line_string(1:(kw_index-1)) 'toc_zxcvb' line_string((kw_index+3):end)];
    end 

    % Check if it is an operation statement that ends with ';' before linefeed
    if (line_string(end)==';')
      cmd_string = sprintf('line_runtime=toc; runtime_info(%0.1d, :) = runtime_info(%0.1d, :) + [0 line_runtime 1]; tic;', line_index, line_index);
      append_cell(line_index) = {cmd_string};
    end  

    % Check if it is a function declaration statement that starts with keyword 'function' followed by a space ' '
    if ~isempty(strfind(line_string, 'function '))
      append_cell(line_index) = {sprintf('\neval(''if exist(''''runtime_info'''')==0; global runtime_info; end; tic;'')', line_index)};
    end

  end

  % Merge append_cell with code_cell to form the test_code_cell
  test_code_cell = cell(1, num_lines+1);
  for line_index = 1:num_lines
    test_code_cell{line_index+1} = [code_cell{line_index}, append_cell{line_index}];
  end

  % Add header comment to first line
  test_code_cell(1) = {sprintf('%% Entry ID: %0.1d.  Author: %s\n', d(entry_id).id, d(entry_id).author)};

  % Write test code to current directory
  code_filename = sprintf('code.m');
  fid = fopen(code_filename, 'w');
  fprintf(fid, '%s', sprintf('%s\n', code_cell{:}));
  fclose(fid);
  test_code_filename = sprintf('test_code.m');
  test_fid = fopen(test_code_filename, 'w');
  fprintf(test_fid, '%s', sprintf('%s\n', test_code_cell{:}));
  fclose(test_fid);

  % Set up global variable to hold runtime-per-line information
  global runtime_info;
  runtime_info		= zeros(num_lines, 3);
  runtime_info(:,1)	= (1:num_lines).'; 
  runtime_info(:,3)	= 0;

  % Run test_code for all, can use multiple game boards 
  load testsuite_sample;
  for board_id = [32]
    test_code(testsuite(board_id).board); 
  end

  % Compute clam signature
  per_line_cpu_runtime = zeros(num_lines,1);
  active_line_index = find(runtime_info(:,3)~=0);
  per_line_cpu_runtime(active_line_index) = runtime_info(active_line_index,2)./runtime_info(active_line_index,3);
  clam_sig = single(per_line_cpu_runtime > mean(per_line_cpu_runtime(active_line_index)));

  % Clean up
  clear test_code; 	% IMPORTANT: clear the test_code in the function workspace so it won't interfere next call
  clear runtime_info;

else
  % clam signature for failing entries 
  per_line_cpu_runtime = single(0);
  clam_sig = single(0);
end




Contact us